A domain availability check based on DNS seems ideal, but a surprising number of domains actually don't have DNS records, so there are false negatives. For WHOIS I guess the biggest concern is recursive / thin whois servers not operated by the registries.
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)