I had an old account on Stack Exchange and I cannot access it any more. I searched my old emails and found mails from Stack Overflow so I know that this is the email address I used for the account. But still, if I try to recover my account, it says that the email address is unknown.
Make sure you're using the right recovery service. There's a separate OpenID service we provide than our actual Q&A site accounts. If you had an account from way back, it's likely you didn't create it with our OpenID and instead used a different one.
Use https://stackoverflow.com/users/account-recovery for recovering an account on Stack Overflow.
Use https://openid.stackexchange.com/account/recovery for recovering a Stack Exchange OpenID account.