Another reason this could happen: Your friends have allowed facebook to scan their accounts and facebook remembered that your friend sent you an email before to the address you're now using to sign up. No scanning of your account required.

I'm pretty sure they do save email data of non registered "users" because I was invited to facebook a few times. There was nothing strange on the first invite, but every consecutive invite had other additional friends of mine, who are too "waiting for me" to join.