How about a new user being allocated a temporary username(*), and that is replaced by their requested username once it has been ok'd. An email would confirm the change.
(*) the temporary username could be a randomly generated combination of common words/syllables so that it looks a bit like a real word and not just a random sequence of letters and numbers. I think AOL used to use this method for generating mailbox names when their '1 month free trial' discs were ubiquitous several years ago.