This is even easier if the operating system partition is plaintext and only the data partition is encrypted. Then it's trivial to modify any binary, library, or startup scripts!
Encryption just means an attacker cannot get at the data right away. But once the admin brings up the system again (not knowing something has been tampered with) it's pretty easy to get access.
The big issue is how to get keys back into the system. I suggest having some onsite tamper-resistant component and some typed in remotely component.
The annoying thing is there is no viable low-end solution for this yet. It makes sense once you're dropping $100-150k of equipment per site, but for 2 servers per site, it's a huge pain and lots of overhead.
as far as low-end solutions are concerned, a usb serial console adapter plus a few machines runs about USD 5K. set machines to redirect console to serial and have an OOB machine for unlocking downed servers.
i'd be interested to hear what kind of solutions there are for onsite tamper-resistant components.
if you have proper disk encryption, it is non-trivial to game the remote physical access to the machine, e.g. attacker convinces someone to use 'remote hands' to reboot server and then gets console redirected pre-boot. if you have disk encryption in this scenario, whether it is on the user data partition or the whole disk, you will surely be notified of the unscheduled reboot and can investigate it.
it is always best to host your own machines (_not_ VPSes) and be able to provide some level of compartmentalization to your hosting setup.