Another way of doing so is publishing the address on the blockchain (in the output of a tx), and only remember : Block Height + Tx Index in the block + TxOut index
minaddress.info is based on similar concept.
If Full Address is 1PPJ5x74KEo9euEiSJKxyBUfHMRQrXKL1f
MinAddress will be 4e0fd-1ppj
Except you can't easily remember as 4 english words.
I have to agree with gmaxwell address reuse should be discouraged. Yes I know people will do it anyways but I would not go out of my way to make it easier. Firstbits was a valid system and easier to adopt/use that what you propose but it was still a bad idea and I am glad adoption died off.
The major problem is that re-use reduces the privacy not just of the person who re-uses their addresses but for everyone else because it makes it easier to track transactions. If all keys were used only once it would make graph mapping the blockchain much more difficult. If you want to enhance your wallet how about reducing the information leak from change addresses. In theory any output can be the change but as practice most wallets implement this so poorly it becomes trivial to determine the change output. There is a lot that can be done to make transactions more opaque so I would consider that an area to improve.
It isn't just wallet designers however. It requires effort from all parties. It would be useful if services provided the option for a user to provide an extended pubkey. For example since people love change addresses a forum like this could have a field on the profile where the user provides an extended pubkey. The site would not display the address publicly but would compute the next address from the extended pubkey and display that. When a transaction is detected it would increment and display the next address. Similarly mining pools could in a similar fashion send all user payments to a new address by just having the user provide an extendedpubkey instead of a static address.
Like I said, an alternative is to publish a stealth address on the blockchain and referencing it by 4 words. It fix completely every of your complains.
I need a solution that work can be printed on an object or in the head without central trust. So I don't consider ext pubkey usable in my scenario.
Also my scheme is nothing like Firstbits, because it does not depends on centralized trust.
If you want to print an address on paper/phone shell/tee-shirt, you have three way of achieving that : Either a regular bitcoin address, either depending on a service with centralized trust weak to replacement (like payment url BIP70), either stealth addresses. Sadly there is no other alternatives.
We can scream all we want about privacy leaking, there is a specific problem and I see only two solution (but stealth address are not widely supported and very limiting because of OP_RETURN limit), privacy leaks are worth it for my users.
Telling them "don't do that because you put others at risk" is not an option. If this is the only downside, I'll implement my scheme with a fixed Bitcoin address and just wait better support for stealth address + a lift of OP_RETURN.