When shopping for domains it's best to start at a small WHOIS provider that you trust to give you a yes/no answer. If you shop at NSI or GoDaddy you will find that the domains you were searching might be registered a few days later. Only hit up GD if you're ready to buy (avoid NSI at all costs)
Interesting, I've long suspected some companies might engage in such practices... I guess one plan is if a domain you want is free right then, buy it immediately. Also, I hate GoDaddy so that takes of that issue...