I would also suggest IETester for testing multiple IE versions at once. This doesn't cover everything but would probably suffice for initial testing (along with your main browser of choice - which I assume isn't IE).
The problem when you get to do your proper testing is you need to test things on their actual operating systems. The same versions of Firefox on OSX and Firefox on Linux can look quite different because they use different font renderers. If something depended on a font being an exact size, this could break things.
So unless you want to build your own render-farm (not as hard as it sounds actually, nor that expensive if you use some virtualisation tech like VirtualBox or VMWare), you're left with doing it online. BrowserShots is good but you do have to pay if you want your shots back quickly. Adobe BrowserLab doesn't offer quite as many options and I'm not sure what the pricing structure is... But it does integrate quite well into an Adobe workflow.