Spammers will add randomly-generated email addresses to their target lists sometimes. Depending on the response from the mail server, it may be possible for them to determine if the address exists, without even getting a reply.
So, if your email address is relatively simple, like a combination of one or two common English language words or names, plus numbers, or a even a short combination of random characters, it's possible to get spam even if you never revealed the address to anyone.
.... Crap. That sucks xD