You can break up the entry of the username/email address and password into two phases with an appropriate prompt depending on whether the user has already successfully entered their username/email address or not.
For instance, on CapitalOne's website there is a "Forgot ID or Customer #?" link before the form entry initially, followed by a "Forgot Password?" link once you've successfully entered your ID. On gmail.com, there is a "Need Help?" link before you successfully enter your username/email address that becomes "Forgot Password?" once you've entered it.
For security purposes, I would block too many failed login attempts (even invalid email attempts) as it sounds like you are, but allow a user to click some sort of "Need Help?" link for support logging in at any time, not just after 5 failed attempts. (Gmail, for instance, uses a recovery email or phone number set at registration to support forgotten usernames/email addresses.)