Larry and I just discussed the idea of having a "lottery" system for usernames which are freed up through an eventual user deletion system for dropping inactive users -- if we even build such a thing.
I told Larry I wanted to build it auction-style, but Larry's not keen on the idea of turning AP into a "currency" to spend on things, and instead came up with the idea of a lottery where we let 100 qualifying users put their account into a pool to "win" a new username. Qualifying, of course, would depend on when you last changed your username, etc.