brotherhood_of_LAN - 4:24 am on Jun 30, 2011 (gmt 0)
>I notice that the registar website can remember your past search without login
Are you sure it's not just your browser remembering what you typed into that form field? It's no biggie if a site remembered it anyway, they could use a cookie to tie you with your searches.
I would check if the domain had backlinks, there are a ton of domains and a ton of methods used to grab domains, particularly ones that already have backlinks pointing to it.