Earlier I tried to create a character with 5 or so different versions of the same name, all of them were 'unavailable'.
So out of curiosity I decided to make a test character and /who the names to check the level of those who took them. Does /who only work for logged-in characters? Because not one of the "unavailable" names showed up on either Alliance or Horde characters.
Also, despite the server's high population I never expected the name game to be this hard, do people just claim names on level 1 characters and leave them there or something?