I tried about 6 different cheap VPS providers and the best performance/cost so far is $11 for 8Mhashes/sec, 4 cores, v0.3.11. That's 11 0.06 = more than 183 BTC/month to get profit. I obviously get less than that, but I'm happy to pay less for my server and support bitcoin network.

1 provider had 2Mhashes for $4, 2 cores, but they eventually sillently went offline and I cannot connect to my server anymore. The rest had below 1 Mhash (but I haven't tested 0.3.11+).

I have never had my account terminated. One of them sent me a notification because they suspected I had some kind of performance problem and CPU cycles were wasted. But when I explained them that it was by design and I couldn't use less CPU, they just said ok.

http://www.lowendbox.com/ is a great site that lists cheap vps hosting offers. There are many and performance will vary depending on the host but, it's a cheap way to test it out. I think this type of thing will depend greatly if the provider oversells the vps servers capacity or not.