Things to consider:
1) Once you've imported your web pictures into your 300 dpi Photoshop file, did you ever expand any of those pictures within the document? Remember, you can't add dpi on those pictures (despite what every sci-fi and spy tv show will tell you about "enhancing" an image).
2) A good way to test the quality of your art (the dpi and such) is to view the image in Photoshop at 100% (enter 100 into the little box on the bottom left). If you can't see any obvious degradation of the image (pixelization), then it should be okay.
3) Vectors are always better, especially for a lot of the classic characters (as long as the vector trace is decent). You could blow those up to the size of a side of a building and they'd still look good. This art is usually found in AI, EPS and PDF format and can be imported into Illustrator. I'd recommend this. I just finished my character collages, and they only have 3 characters that are non-vector (see my avatar).
4) Most of the large format printers I've encountered (mostly HP) have been 120dpi. I've even gone down to 72dpi and it still looked "okay" (although I personally wouldn't go below 100dpi). Whenever I was forced to use web images in my my old graphic design job, I used to create a file to the size I wanted in Photoshop at 120dpi (100 if I was desperate), and then import my web photos NEVER sizing them up.
Hope that helps. See if you can get your hands on Illustrator. You'll like the results.