This is something we have to deal with every day. People come in with an image the size of a business card or -better still- stolen from a website and ask. "Can you blow this up to the size of a bill board" or "Can I have this on the side of my lorry?"
I used get it ALL the time at the company I last worked at.
Sometimes the logo would be so lo-res that I could hardly make out what it was.
I even made an info-graphic to give to clients to explain the difference between vectors and rasters, lo/high res.
If the image is high quality to begin with, you can resize up without losing too much quality, using Perfect Resize or a similar plugin. You do still lose a bit, but for large format print, it's often acceptable as the viewing distance tends to be further away. 72dpi images, nothing you can do. I often end up tracing logos, finding them on brands of the world, or extracting them from PDF annual reports that I find online.