Many domain whois checker sites log the domain names and sell it to the 3rd parties.
So the safest way to check the domain name availability, is doing it from your computer! No logging, no need to be paranoid :)
Open Command Prompt Run nslookup -type=ns domain.com, if it lists the nameservers, domain is not available
For Linux, *BSD or Mac OS X:
Just run whois domain.com