I've used www.icdsoft.com since 2002. They've been absolutely fantastic in terms of service and reliability, they always answer support tickets within minutes and have gone way beyond what I expect (including once retreiving a database I accidently deleted from their backups, which is amazing for a $5/month plan).
They are based in Hong Kong and bill in US dollars.
Just for contrast, I also use 1and1.com which, I believe is UK based. 1and1 offers far more resources, for the same money (and has cheaper and more expensive plans), but their service is lacking, and realisitically, how much space/bandwidth are you going to use? The reason I use 1and1 at all is they support multiple domains on one account / one service plan, which icdsoft does not.