It is certainly slower but what i always did even back around 1999-2000 when i first learned web programming, was to simply query the user db to see if any user exists with the requested username before even doing anything else. Also at some point i decided to also store a "broken down" version of the username with symbols removed, Os replaced with zeroes, etc and check against that.

Also i never allowed less than two letters and characters that weren't numbers, latin letters, a space and a few punctuation symbols.