We're a small webdev company with a handful of servers.
Every administrator has their own account on every server, and usually logs in via certificate. However they can also log in via password, since they may need to log in from a remote location where they may not have their certificate with them.
Directly logging in as root is only allowed via certificate. We haven't completely disallowed remote root login, since it is very useful for transferring files between servers via rsync and scp, however only the most trusted administrators have their certificates added to root's authorized_keys file.
Administrators get superuser privileges via sudo, by making them a member of the wheel group.
This does not protect against malicious administrators but it does provide some logging, and the ability to disable individual accounts, when an admin leaves. It's also doesn't scale well, but is fine for a small numer of servers.
Scripts which need superuser privileges, such as Capistrano which we use to deploy our websites from version control to the webservers, get their own user accounts and can use sudo to perform superuser actions. But, they're limited to only the commands they require, via sudo's Cmnd_Alias.
I'm thinking about setting up Likewise Open so we can tie the authentication into our Active Directory domain. This would make it easier to centralise the authentication, manage passwords, and provide granular permissions.