To answer your question:
Genuine Fractals is a (somewhat expensive) plugin that some folks recommend. I used to use it but lost it in a pc upgrade some time ago. Do a search here, I remember Michael reviewing a couple of other products.
Check out www.fredmiranda.com
- he has an action that gives good results by applying the bicubic interpolation in 10% increments. I use that method, although not his plug in.
Other folks recommend Q-Image which has some different algorithms. I think you can download a free trial.
In my experience (D30 and 1D) going to 13x19 - other post processing techniques (ie other than how you upsample) can have just as a great an impact - most particularly around sharpening, but also in how you deal with noise - sometimes what appears to be noise free at 8x10 becomes noticable at 13x19.
I don't know what kind of printer you have now - but if it's a good quality photo printer, even if 8x10, I'd do lots of expirementation with crops printed out at 8x10 before I start to think about third party...
One other factor is the quality of your monitor callibration and existing printer profiling - just because you might be happy with the output from your "home" set up is no guarantee you will like what comes out of a commercial operation - again testing their output at a smaller (more economical scale) is mandatory.
Finally, if you know in advance you are shooting for an extreme enlargement, use all the technique you can to get the best shot from the beginning, ie: tripod, RAW, expose to the right, optimum f stop, regardless of the shutter speed, it can't hurt to use MLU & 2 sec delay, etc. etc. ...