ARGH. This is a usability nightmare - moreso when the recovery system implements the same rule.
"Okay, I had an account on this website, which email address was it again?"
try logging in a few times
"Hm.. I must have forgotten the password. Off to reset!"
go through the recovery process
recovery page indicates an email will be sent
email never comes
"Wait, so are they being 'really secure', or is email just broken right now?"
wait a couple hours
forget about the site
(which is why I think that indicating specifically, that the userid was incorrect or the password was, is better UX.)