how do you manage servers' root passwords

The systems I run have a sudo-only policy. i.e., the root password is * (disabled), and people have to use sudo to get root access. You can then edit your sudoers file to grant/revoke people's access. It's very granular, and has lots of configurability---but has sensible defaults, so it won't take you long to set up.

I would normally suggest the following:

1. Use a blank root password.
2. Disable telnet
3. Set ssh for no-root-login (or root login by public key only)
4. Disable su to root by adding this to the top of /etc/suauth: 'root:ALL:DENY'
5. Enable secure tty for root login on console only (tty1-tty8)
6. Use sudo for normal root access

Now then, with this setting, all users must use sudo for remote admin,but when the system is seriously messed up, there is no hunting forthe root password to unlock the console.

EDIT: other system administration tools that provide their own logins will also need adjusting.

While it is a good idea to use a sudo only policy like Chris suggested depending on the the size of your system an ldap approach may also be helpful. We complement that by a file that contains all the root passwords but the root passwords are really long and unmemorable. While that may be considered a security flaw it allows us to still log in if the ldap server is down.