It seems to me that sshd should not tip its hand by returning different responses when a user ID can be used for logins than when it can't -- allowing an attacker to focus password guessing attacks on user IDs with which it would have a chance of gaining access. For those folks out there who are more familiar with OpenSSH than I am: How hard would it be to make the responses indistinguishable?
Are you running the latest version of portable OpenSSH? If not, you need to upgrade. As far as I know, there should be no more leaks of this sort in the current code. If there are, please notify the openssh developers (and include your authentication configuration - your PAM modules may be leaking the info, and there's nothing OpenSSH can do about that).
-- Carson