At that point, why stop at separate uids and not just use separate virtual servers? It's a bit more costly in space and RAM (when running), but it's pretty good at reducing the attack surface. If you really want to be paranoid, restore from a snapshot every time you start the VM, and occasionally start it just to update it and create a new snapshot. Even if an attacker does get a local account, they have to do something useful with it before you close the virt, essentially destroying anything local they've set up.