And if for some reason Amazon isn't suitable, you can get dedicated servers seriously cheaply these days too, e.g.

http://www.hetzner.de/en/hosting/produktmatrix/rootserver-pr...

(no affiliation, I'm just a happy customer)