Are you still getting the same type of error message as first reported?
I traced through the email code: STOREDIRECTORY/includes/functions/functions_email.php
That error message is provided (failed validation) if it doesn't pass the zen_validate_email function... If the email truely is of a valid type (Ie., properly formatted) and the code has not been changed, then you may have an observer that is looking for: NOTIFY_EMAIL_VALIDATION_TEST that is modifying the $valid_address variable to state FALSE... Check using DTK to see if that notifier is being listened for.
In a search of my files I only found that in one location, the function itself...
Bookmarks