Yeah it's true. Just want to share my experience... I've used PayPal since 2005 using my gmail account, and get verified. Used it often until december 2010 and woilla... I can't log in... I try to use "problem signin" section and magically... it say "We couldn't find your email address. Please try again or select I don't know what email address I used."... hahahaha.. great job... sent an email to paypal on january 2011 and they ask me to create a new account... well.. ok... I sign up for an account... but.. I can't use my bank account to verify my PayPal account... why..? they said that my bank account number has been attached to another PayPal account... hmmm... let see... hmm.. ok then.. manual verify would be ok... great... i sent my scanned ID card and bank statement.... wait for 2 days... and voilla... I got verified.... nice.... but today... again and again... I can't login... I assume I've lost my password... ok... request password reset... and magically... "We couldn't find your email address. Please try again or select I don't know what email address I used." shows up... I guess I've had enough with PayPal... Still shock..
That is the email address where you received notifications from paypal. You should remember it. Better luck next time.
If this is the case, keep on call up paypal service center and complaint about it, you have right to ask them to solve the problem
Same thing happened to me and wanted to share my experience. Yesterday I tried to sign into my account like any other day and after copy pasting my info from my passwords doc I got an error message saying my email address is not associated with any account on Paypal system. I copied and pasted my info couple of times and tried entering them manually and nothing worked. Then I Googled the issue and found this tread. I though Paypal deactivated my account but I wanted to give it a try and keep trying since I am outside the country and there is no way I can create a new account. I clicked on forgot my password link to recover my password and got the same message saying system doesn't recognize my email. After couple of tries I realized another clickable link on that recovery page that sounded something like recover your password or forget your password (don't remember exactly). I was already on the recovery page but tried clicking on that as well. That link took me to a second password recovery page where it was asking for 3 email addresses that I think might be associated with my account. I only entered one since I only use 1 email and clicked ok. To my surprise I got a message that said we located your account and took me to verification page where I had the option to choose verify by phone or email. I did the email verification and after waiting 15 - 20 minutes and multiple re-send verification code I got nothing. So 40 minutes into this issue, right before I was giving up and leaving work I decided to give it a try on another browser. I closed my chrome browser and opened Firefox and entered my login info. BOOOM I was in!!! No error messages, no fuss, from FireFox I was able to enter my account right away!!! Incredible no?? I mean I spent 40 minutes trying to login to Paypal from chrome and constantly got email is not associated with any account message. I honestly though Paypal for some reason de-activated my account!!!! This is a bug in their system and might be a Chrome (Browser) issue!!! There is definitely something wrong with Paypal, though I don't think it is a common issue since I have been using Paypal for years and experienced this bug for the first time!! If anyone having the same issue try signing in from another browser!!
PayPal won't terminate accounts without contacting you. Unless you've simply forgot your login email, then you should have something in your inbox stating why your account was terminated. Terminated accounts are not completely removed either. You should still be able to login to receive a "your account is locked"-type of message.