hmmm you must have some back link somewhere, Google can't just find a new site without it being link to from somewhere else.
Google is an awesome machine. I have had similar experiences with new domains. The existence of a link on a webpage endowed with moderate PR, and a bit of luck, is all you need.