rackspace

ホスティングサービス大手でVPSサーバーも提供している。

http://www.rackspacecloud.com

最小構成で256MB Memory/10G Disk、１時間あたり0.015ドル。
面白いのは最小構成から64bitになっていて、再起動だけで15GB Memory/620GB Diskまでスケールアップ可能。
CentOS, Ubuntu, Windows Serverが公式イメージとして用意されている。
ただし、サインアップ時にRackspaceから直接確認の電話（英語）がかかってくるので敷居が高いかも。