Actually not. Just use a loopback cypto FS to store the sensitive stuff. The reason they had to reboot the machine is that they just had access to the HDD where they could change the password, as opposed to having live root access.
If that's even the case here. We don't have much indication that the attacker couldn't have taken a snapshot of a running system (or that that will be how it happens next time).
So, sure, use a loopback crypto filesystem. It just doesn't provide much in the way of a security guarantee (but it adds some measurable costs).
http://www.debian-administration.org/articles/152
You can also require a password AND a cert.
I mean, I'm very clearly not a crypto expert, but I do believe that this would be quite a lot like what Bruce Schnier calls 'the evil maid' attack. Instead of having a bootloader, you have a minimal Linux install, then you get a key to that minimal linux install, and that minimal linux install uses that key to decrypt your encrypted disk.
I believe that if that minimal linux install that does the decrypting is compromised before you log in, in theory, the attacker could then insert something in the code that runs after the data is decrypted to, say, send some of that data elsewhere, or, say, open a back door for them to log in and examine the decrypted data.
I mean, certainly, you are making the attacker wait for you to log in (assuming that they've only compromised the admin interface and don't have full root on the dom0) and that's another step you are forcing the attacker to take, and you do at least have a chance then of detecting the compromise and /not/ sending the key, so I'm not saying that it's worthless.
Of course, this is all protecting against a compromise of the admin tools that does not lead to a compromise of the dom0. If the attacker compromises the dom0 without rebooting it or otherwise disturbing the guests? they have access to your ram. They can snapshot both the ram and the disk and take apart the system at their leisure.
I don't think I've ever met a professional sysadmin who could defeat the evil maid attack. All the ones I've met would refuse to think about an attack vector if it implied they could not boot their servers.
Any sysadmin that claims to be able to protect against a physical access attack or its contextual equivalent is either lying or incompetent. In neither case should that sysadmin be considered "professional".
The evil maid attack would be useful against the system admin's workstation. Securing NOCs is beyond the scope of this discussion, but it is not difficult.
If you can memorize it, it is a bad password.
This may be oversimplified, but it's the correct horse battery staple.
Then that scrap can be securely stored somewhere else. (eg: In your "in case of death" box if you want people to have access when you die.)