What is best place to look for reliable, legitimate international web hosting?
Ideally I'd prefer a dedicated machine, but would settle for a VPS solution if the company was right.
I'm looking for EU, Asia, and South America.
One thing that you can try is to search for your keywords
On Google's international sites, you have a radio button that can be clicked to restrict the search to sites in one country, so you can plug in to the local web hosting community.
For the EU, try http://www.google.co.uk
For Asia, try http://www.google.com.my/ because Malaysia has a lot of English speaking sites and the tech business community there tends to work in English
For South America it is a bit harder since English is not widely used. The biggest country with probably the best connectivity is Brazil http://www.google.com.br. Of the Spanish speaking countries that I tried Venezuela did come up with a lot of English ads http://www.google.co.ve/
I know you said that you would "settle" for a VPS, but consider that many VPS hosters are able to quickly recover VPS servers from hardware failure. Either they use XEN and can migrate live servers to another host, or they use OpenVZ with the virtual hard drives on a storage system so if the physical server fails, they can quickly reboot all the VPSes on another server.
In any case, you can search with