first of all you'd be dealing in ppi not dpi and it really depends on the image, or rather the amount of detail.
But I would say anything more than 500dpi is pushing overkill.
I tend to overkill, but also because I crop like hell. What you need to do is find out that printers LPI ( lines per inch) and , for overkill sake .. multiply by 2.5.
As a point of reference a news paper is 85lpi, a nice news paper is 120lpi, and a regular mag is around 150lpi.. and most of these medium work with graphics that are only 1.5 times their LPI anyway, so my 2.5 includes overkill)
So if they tell you they print at 210lpi, your graphic is pushing EXTRALAGE at 515ppi.
Here is WHY , in the age of broadband and DVD oversized images can be bad:
1) they tie up the RIP
2) and this is what matters to me, really, print houses sometimes ( read: MANY TIMES) tone the images to match the calibration of their printing equipment... After all whats the use of "sharp" images if the color is wrong, right? This means that if you send TOO much information (this is why 1.5 - 2.5 the LPI is optimal) then what you have is the color information of all the pixels above what the printer equipment can handle gets "averaged" ... poof there goes your color accuracy ...
The point is: call your printer, ask about toning curves, and lpi and use 1.5-2.5 the lpi and you will be golden.
OH .. and I hope you aren't thinking of merely "upping" the resolution on a low res image.... BAD BAD BAD ( if that's not the case, I hope I haven't offended your intelligence these days is best to cover all bases )
EVERYONE HER TYPES FASTER THAN ME
About billboards... billboards are a different matter all together. IME, billboards have the same DPI as newspapers or even flexo. If you get up to 5-6 feet from a bill board pixelation in images. The thing is, unless you want to inspect a model's nose hair, most people dont see a billboard from 6ft away... more like 60 yards... and usually at speed. so you have lower resolution but a larger size.. averages out to the same effect on a billboard.