My favourite site for searching for available domain names is Instant Domain Search. It uses AJAX to search the availability of the name as you type it. It’s really fast, so it’s good if you are trying many variations.
It seems however, to simply do an NSLookup to determine availability. That means that if a name is registered, but not pointing anywhere, it will show up as available, even if you can’t now register it. This is a pretty rare occurance, so I still use it, but just be aware.
