I have a client who has an osCommerce site. When a user tries to register they receive this error even when their email is valid. I entered my own email address with no luck as well. I checked the configuration and "Verify Email Addresses Through DNS" is set to false. What else could the problem be?
I know, not very pretty, but it's what they got :