Does the email address even exist? Mailboxes are flagged for deletion if the user doesn't sign in at least once every 180 days. The help page Deleted Email error message explains more.
So first you'd check if the email address is still active. Send the email address a mail message and see if you get an immediate bounceback error message saying 'Undeliverable' that means the mailbox isn't active.
Then enter the email address at Verifalia, an external website that verifies if an email address exists. Enter the email address, complete the reCAPTCHA and select the Validate button. Does the top line response say 'Deliverable' or something else?
Finally, use the Reset password now button in the Help page Changing your email password to see if you get a deleted or no domain error message or if you actually do have password recovery options saved.
Let us know the outcome in each case.
