I think using an email address (and/or a uniquely generated username), as an identifier is the best comprimise. Then a generic 'credentials invalid' => retrieve your account: 'enter email' page to reset passwords. And require a confirmation click from your email for two step sign up.
You could always sniff out if someone has an email address on a lot of systems by visiting the 'forgot your password' page. So perhaps on the account rescue page, just ask for a valid email address, then give a generic thank you message. If the email address exists, send out an email, if not don't bother - but don't give feedback of the sort 'that email address does not exist on the system' etc.
I'd suggest that your last point is providing a bad user experience in the interests of privacy. Many people (myself included) use these forms because we've forgotten our password or at worst forgotten the email we used to sign up. I have about 5 different email addresses I use for various things so I'd be quite disappointed to see a thank you message if it wasn't the email I had actually used to register. There's also the use-case where people mistype their email address.
If you are worried about email mistypes then you could always provide a confirmation. However I'd have thought we'd be pretty good at getting our email address right, and the browsers a lot of the time provide a magic autocomplete for email addresses. I guess it just sees a form input name attribute of 'email' and goes by that.
Multiple email addresses are a pain I'll grant you that. But no worse that a multitude of user names.
Perhaps a better message might be:
'If your email address is registered, then we will attempt to send out an email containing a reset code. Please check your inbox.
If you do not receive an email to your given address, then you may not have registered with given email.
Allow time for the arrival of email, and please check your spam folder.'
But it gets a little long winded... I'd almost rather not have a password, and be sent a new code each time (albeit transparently).
I invariably forget passwords and logins frequently. So go through this process like you as a matter of routine.
Bad times potentially though for when your email service is down or when your email address has expired. Or your email account has been exploited.
You could always sniff out if someone has an email address on a lot of systems by visiting the 'forgot your password' page. So perhaps on the account rescue page, just ask for a valid email address, then give a generic thank you message. If the email address exists, send out an email, if not don't bother - but don't give feedback of the sort 'that email address does not exist on the system' etc.