Please, I'm not some domain god (which was the greeting in one fax I myself
answered before :D). I don't profess to know all the answers, but I'll share a
few that I've learned from having worked in the business.
When one uses the registrar's site to make a domain availability query, they're
going to query the Registry of that extension. If you're looking up for a .com,
then the registrar will check the VeriSign COM NET Registry.
That query is not shared with other registrars. However, I will grant that the
registrar can very well share their results with others if they choose to.
Unfortunately that's not going to stop others from getting creative. The port
number registrars use to do those queries is also open to data-mining.
If your machine is "compromised" by spyware or the sort (knock on wood) or if
you're using a toolbar, you might want to also check if they're not sharing any
query with someone. It's not inconceivable.
There are various possibilities as to how and why our domain searches appear
to be seen by others. Without further digging from those involved in the biz,
we'll never really know the full story.
But I'll tell you this: the moment you log onto someone's site, you really have
no realistic expectation of online privacy.