I don't trust any registrar anymore. When I want to know if a domain is available I do a DNS lookup on it's NS records instead of using their web interface or w

I don't trust any registrar anymore. When I want to know if a domain is available I do a DNS lookup on it's NS records instead of using their web interface or whois. It will just hit the root servers and no registrar will know that I did this. Maybe it is paranoia, but I too have lost some domains that I wanted in exactly the same way you describe.