Try www.kimsufi.com .. they have ridiculously cheap dedicated servers. I'm using one now, but haven't had any "real load" yet.

Or if you insist on getting a VPS, how about www.gandi.net ?