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.
So, no providers are truly profitable for bitcoin generation?