Just a few quick thoughts on your problem. If it were me I would probably do the following ..
Check out the workstations with some of the users accounts to see what software is running. I would check out the services on each computer to see if they rely on the system account or a service account to run. I would pay particaler attention to data bases and client server applications if any. This should let you have a good idea on the down time necessary if you do have to reset the administrators password.
ZT3000 idea on the images is a good one but i would take it one step futher. Most disk imaging software nowdays lets you browse the image. that means we can copy the sam file from the image and brute force the different accounts in it without too much down time on the machine concerned. Can also do the same thing with a linux boot disk.
The thing that would worry me is the conditions under which the old admin left. If they were not the best and there is an internet access i would change the password on the different administrators accounts as soon as possiable. It might be a bit of a headache but the down time lost due to changing the password may be less than the time lost from a virus attack.

In anycase i wish you the best of luck and hope my answer isnt too confused as i type it quickly but took a while to send it.