I stopped using them because I've had two domain names registered away from me within 24 hours of searching for them on the site. Ironically, one I looked up before I got on the plane to the 2006 startup school and by the next morning when I had network access it was taken. It may just be bad luck but I've never had that problem with a generic whois or providers like GoDaddy.
I had something similar happen and I emailed the instant domains guy and to his enormous credit he took the time to look into it and dig through his logs. Odds are that you and me and tons of other people are just victims of domain kiting (google it). Bad guys register tens of thousands of domains on spec for nothing. It sucks, but wait a week or two and your domain may reappear
Incidentally he said the site is actually using an internal list of domains that I think he got through some sort of DNS trick. It doesn't make any outside queries.
Usually in those cases your domain name might reappear in a few days, since there are some 5 day money back policies that the domain hogging companies take advantage of.
