I'm paranoid about that too, ever since it happened to me a couple of times with various registrars, godaddy comes to mind for this once. I never run a single domain search on big domain seller sites anymore if I'm really interested in something.
I also seen this happen when running a domain name through certain domain info search tools to see any history or anything. If you use anything like that, don't wait to long after to reg it. I wouldn't be surprised if people put these tools on their sites just for that very purpose.
It makes me even more paranoid when it happens to be an abstract name that you make up... I mean what are the chances right?
Could be just coincidence but it's just so disappointing when it happens.
Best bet is to sneak them into a bulk search. If they want to get your name bad enough they'll have to register them all.