uwhois.com will search all the top-level domains, but (for example) searching for google.com results in a selection of "google.com.and.stuff.here.from.stupid.scammers.com" results.
Possibly still okay for me, but it's not really a reliable check. :/
If I want to do a specific/exact search, I can only check 10 TLDs per request, and three requests in too short a period gets you locked out for a period. :( Searching all 250+ would take /ages/
OOOH! I think www.markmonitor.com is doing good. Still not an actual web service, but it's returning useful results.
I think specifically registered rather than just a DNS lookup (but not sure at the moment).
This is for my hosting thing - it needs to confirm that people already have a valid domain before signing up, rather than them assuming the domain will be registered on their behalf.
(Which I might look into eventually, but for now I just need the simple path working).
