Password Management for Administrators

We have had two domain/enterprise level administrators leave the company in the last 6 months. This means that in addition to disabling theirr accounts, we have had to change a large number of passwords for service accounts, local admin accounts, infrastructure equipment, etc., basically whatever they may had had access to.

What tools, methods and policies are other administrators using to make this job less of a pain?