So I now write them down.
I've downloaded and now use Password Safe, as it keeps a database of all the passwords and usernames you'll ever need to know. Small program, easy enough to use, and it encrypts the database using a reasonably strong encryption algorythm. Now, all I need to do is pick up one of those USB keyfobs and keep the program on there, so the database won't be stored on any computer and anyone creeping around my computer at night won't be able to get at it.
Still sucks, though, they were safer in me noggin; the unreliability of retrieval just got too high.