However, if you rent a VPS, and you mine, you'll probably be kicked in a matter of hours/minutes
Not necessarily ....
A few months ago I tried some mining on VPS from DigitalOcean for a test. I delegated 3 out of 4 cpu to mining and they kept mining for a month without any interruption from provider site. The effects were not stunning - after all, the parameters of inexpensive VPS are not perfect, but I found out that it is completely possible...
You are right... I was speaking from my (limited) experience with VPS's and from reading other people's stories on BTT. This does not mean there is no VPS provider out there that doesn't allow mining. As a matter of fact, the odds are big that there are a couple out there that don't mind (or don't care enough to keep an eye on their host's load).