It may just be coincidence. I've registered domains and found they were previously listed on available lists.

Of course, I wouldn't chance it and use Whois Source to check domain availability.