We type the passwords in and print them using a console or OCR font. After verifying, the document is closed without being saved. The passwords are then sealed in an envelope and stored in the CFO's safe of all places. Somewhat regularly, the CTO and CFO open the safe, verify it's still sealed, and have the admins make new envelopes.
Separately, the CTO maintains a backup admin accounts, with the passwords stored off-site with the backup tapes.
We haven't totally gotten the hang of what to do when a password is changed, because there are services that fail to start when an admin password is changed — but it happens rarely enough that it's not too big of a deal.
The envelope trick actually did come in pretty handy when the most senior sysadmin developed a terminal medical condition and passed before a full turnover of duties was complete. Unfortunately, with him knowledge of some of the cabling routes was irretrievably lost, and we have problems with this to the day — years and years later.