Originally Posted by WiredGuy

It certainly is possible, chances are there are links just that the search engines haven't updated their backlinks. Its also possible someone submitted your site directly to a search engine. Also remember that Google is now a registrar and knows every domain that exists. There's many possible reasons, post your domain and a more useful answer can be given.
WG