Local Administrator Password Solution

Where do you store the password of the local admin account on every PC in your domain? Options include:

• The account is disabled, only use a domain account/group for local admin rights (what about when the domain isn't available?)
• Use the same password on every machine, set at the time it is built (great way to allow malware to spread across the entire network in seconds!)
• Use a spreadsheet or other centralized notes to record them for other admins to access-but it's okay because it's on a secure network share and password protected (because no one could possibly make a copy or crack the weak security of Excel, right?)

And what do you do when you want to change the password after your system has been compromised, or one of your admins leaves, or a user has discovered the password and is now using it to install software and...