The civilians, yourself and myself among them, live among many other civilians who are unwilling to act to preserve their freedoms. Reminds a bit of the parable about evil being more about good people doing nothing rather than evil people doing bad things.

Yeesh, if they're trying to do cleanup behind themselves rather than e-mail you to let them know they'd rooted the box, it's time to switch. This goes double if (and, you may have specified regarding this; apologies if you have) you've already asked them in writing to never jump into your box without asking you first.

As others have said, if the provider has physical access, you can not expect mathematically no chance of them breaking in and grabbing or (worse) changing stuff.

Focus on what you are providing and just how secure it needs to be, and act accordingly.

A really nice host carries machines with remote management built-in. This goes double for x86 or x86-64 where the architecture didn't grow up with the idea of "the text put up by the systemboard's ROMs can go to a monitor and/or to a serial port."