And only if that comes back negative, do a whois. If you're really paranoid, run your own recursive DNS, so your recursive hits the TLD servers itself. TLD servers aren't going to log checks for names they don't have; they've got better things to do; registry whois servers probably aren't going to log either, but whois shows more intent than DNS queries.
host -t ns reallycoollname.com
Unfortunately there is no perfect method. I've had this happen to me before, and am starting to believe it was just coincidence. I think there are too many domain queries globally for someone to look through, so I'd suggest not searching a name too often and you're probably good.
(I'm building a faster domain search based on DNS and WHOIS data)
It would be great if someone wrote a script to query random domains at a dozen registrars to bilk these front-runners into wasting money on worthless domains.
Perhaps investing in an antivirus or antimalware package would alleviate your problem.