A lab may be able to help, though just so far as to enlargement size.
I recently purchased Qimage Pro. I've been hearing about it for years and finally had a need to print out top quality photos. I'm impressed.
I was not in your situation, but I have heard it does a good job at enlargement from lower resolution images. You have nothing to lose to try.
You can download the Pro and Lite versions and try them for 30 days free. You may also want to start with the easier-to-use Lite, as the Pro interface can be pretty intimidating in the beginning:
http://www.ddisoftware.com/qimage/Here's a link to the Lite version:
http://www.ddisoftware.com/qlite/They are priced $50 and under.