EDIT - Hey down voter(s), checkout the paper. I'm guessing you're afraid of a reasonable debate in this space. Perhaps, we as a security community are inflicting unnecessary pain on our users. Is it worth exploring?
I've always wondered about password rules and felt they might not be needed.
This paper argues (quite effectively) that we should reconsider secrecy of the UserID and dump complex password rules. That is, do not use public information (like email address) for User ID and instead have the organization assign a user ID. If you consider the total entropy of the account, i.e.
log(UserID)+log(Password), then a larger and not easily guessed User ID works against an attacker, meanwhile the User can set their browser or their app to remember the User ID. User can also keep a file (encrypted or not, it doesn't matter) with site/application/user_id mappings on the computer.
If you want to argue that this leaves the user open to malware attacks, well, then, complex passwords won't stop that, either.
If you want to write the ID on paper, then (1) lock it in a drawer (at work/home) or (2) leave it hidden somewhere near the computer (at home). A Real Attacker (tm) with physical access to a computer has many options beyond needing a user id (or even a password). Physical key loggers, disk copies, single user and external drive boots, etc. If the computer is at home, a human close enough to steal a user id off paper (locked away or not) is the least of the computer owner's worries.
Still, keeping an electronic copy of the User ID on the computer is just fine. We are defending against the most likely attack here (password guessing over the interwebs), not the least likely.
One of my financial institutions does this (assigned account ID) and allows a numeric password. I feel my account is quite safe.