Sorry for the self promotion (what's our spam policy on this?), but I felt that this audience would be more interested in the content :)
This post describes why it's a bad idea to assume the security of your machines if you host them on a VPS provider. The only secure server is one that you have exclusive physical access to.
The thread posting sounds like a roundabout (but very detailed) way of saying your VPS provider is running your server and anything they can do with the host key, they could just do by installing whatever they want on your actual VPS instance.
It seems kind of moot when you're using a VPS though. Aquiring the host key would open up man in the middle attacks, but the VPS provider is also the "man at the end."
It goes on to say "replacing passwd" and such, but that's not necessary. One could just replace the file with dd or boot via single user. Potentially, one might also be able to hotswap an executable image on a running machine in memory, but I never tried it.
In short, physical access to a machine is game over and everything else is just kind of over verbosity that gets to the same point.
If you are using a shitty virt type like OpenVZ, all they need to do is do vzctl enter [your_vps_id] and they are at a root prompt. This is hidden from w/who/last/ps.
This post describes why it's a bad idea to assume the security of your machines if you host them on a VPS provider. The only secure server is one that you have exclusive physical access to.