I hold as a rule of thumb that A3 size (42cm x 29.7cm) at 300 dpi is the largest you need, ever. When sizes go up, the dpi goes down. The best reason for this is simple, prints that size will be looked at from a greater distance. And most production methods for largers sizes do not actually use any more dots per inch, so it is wasted space and computer power. For enlarging I use Genuine Fractals, but have used PhotoZoom too. Actually, enlarging in Photoshop, and trying different interpolation methods might be just as succesfull. I am not seeing huge differences in quality. Ideally you should start with the largest originals you can produce. Enlarging always involves 'inventing' (interpolating) new pixels, so the more pixels have to be created, the blurrier the end result will be. Enlarging beyond 400% will really start to degrade the end result (it will start to look like a water painting more and more - but that does not have to be a bad thing). So: large originals and a resolution that goes down after sizes that surpass 42 cm (16.5 inch). Some people insist you should enlarge in steps of 10% for the best result. But that takes a lot of time. And I don't think anyone will see the difference once the billboard is out there.