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.