(I'm one of Domainr's co-founders, and for the record, we absolutely do not, and will never, do anything ethically ambiguous like front-running.)

We hear of similar issues from time to time, and each time we've investigated, they've ended up being coincidental. The thing to do is look at whois and see when the domain was originally registered — perhaps GD is showing domains with varying "already-registered" states in their search results:

http://domaininfo.buydomains.com/domain-name-basics/domain-n...

Another (creepy, imho) thing to keep in mind is that Verisign allegedly logs and resells aggregate data from unresolved DNS requests:

http://www.domainnamenews.com/editorial/verisign-to-profit-f...

(Domainr uses the DNS to check for availability — it's hella fast, and sufficiently accurate to provide a good user experience.)