Wow, I hadn't checked Prgrmr's rates in a while. Their smallest is now $5 for 64MB of ram, and for $20 you get 1GB.

http://prgmr.com/xen/