I think to make it really useful you should be comparing all of the permutations (at least for one of the columns) for me without me having to click through each one by hand. If I give you a word it's already pretty clear that the word is taken and I'm looking for alternatives.
For example, I had this hosted on Heroku for a while and tons of requests were failing because Heroku uses shared IP addresses for all the sites it hosts. Evidently I wasn't the only person doing domain availability checks from their network.
Also, the UI would get pretty nuts right?
Basically it just does a whois lookup on the domain and I don't think I could replicate that behavior from the client side.
Edit: This comment says it would be possible http://news.ycombinator.com/item?id=5132750