When you use the Lost Password form and enter an email account which doesn't exist in the database, there is a valid error message:
The requested member could not be found.
A password reset request has been emailed to you. Please follow the instructions in that email.
A little check and warning like the "Please enter a valid email." you have in place for the contact form when the e-mail field was left empty would be a good fix for this situation.