If the company wants all the security -then show them that the only way to do what they want is with a 3rd party security package.

OR

You could use a NIS root account - this is how -
You have your normal root account which has it's info in /etc/passwd (and shadow). If the server looks at NIS before files, then you could have an NIS root account - one password for all servers (yes, drawbacks to that too!). If NIS was unavailable, you would have to know what the server's local root password is to log in or su to root.

To change passwords on all servers requires setting up some type of allowed access - there is a 'free' product called cfengine which worked well (although our site lost 46 servers in one minute due to a bug {which was fixed but we never used it again}). Another way is if you have programming knowledge is to write your own.

My own opinion is with the 3rd party software. I've seen it work and it makes it easy to use (this was on a mix of Solaris and HP servers). I think RSA Security makes/sells it.