I deleted my Facebook account a few years ago through this process. I was very careful not to log back in, and when I tried a few months later I was rejected - no account linked with that email address.
Six months later I signed up with a different email address, and Facebook forced me to confirm my account with my phone number. Javascript Error - that phone number is associated with another Facebook account. I click OK, and I'm redirected to my "new" account with all my old Facebook friends (on the opposite side of the country) showing up as "people I may know."
The other possibility is that it's people that have looked up your name on Facebook before you had an account. So HQ logged it as X wanting to find Y. When Y makes an account, we'll let him know X was trying to find them.
Six months later I signed up with a different email address, and Facebook forced me to confirm my account with my phone number. Javascript Error - that phone number is associated with another Facebook account. I click OK, and I'm redirected to my "new" account with all my old Facebook friends (on the opposite side of the country) showing up as "people I may know."
Nothing is deleted from Facebook, ever.