Som allerede nævnt skal du, hvis du ikke vil ned og vende på serveren, sende alle optagede navne med ud i javascriptet i fx et array. Med mange brugere vil dette blive langsomt og samtidig skal du stadig tage højde for at to brugere i teorien kan forsøge at oprette det samme navn samtidig.
Når du taler viewstate osv regner jeg med at du taler om ajax.net og ikke ajax som teknologi - for der er intet i vejen for at du laver din egen funktionalitet og så er du helt uden om hvad .net laver (se fx
http://dengodekode.dk/artikler/ajax/xmlhttprequest_wrapper.php) og så er hastigheden kun hvad serveren og du som programmør formå at sætte sammen.