It really depends on how paranoid you want to be. Removing their SSH keys and changing the root password will prevent casual snooping by rack-monkeys. If they need to change any hardware other than a drive they'll have to shut down the machine and you'll probably notice the gap in uptime. Keeping crucial data encrypted at rest will likely prevent pulling a mirrored drive and copying it. If that isn't enough security then you'll need to colocate and physically lock down the hardware yourself.