This may sound stupid but i bet its not an email problem. Ive posted a similar problem on this forum about 3 weeks ago but the difference was i was doing a bulk user upload. I recieved the exactly the same error. The solution had absolutely nothing to do with email addresses. The error was actually too many users in my CSV file.
Im not suggesting this is your problem but i have now come accross 2 other instances where the error msg is not accurate. Have a good look at all your settings. Ignore the email address error for now and see what else could be the problem. I just tested UK extension with my moodle and no problems.
The other place i get an email error is the ID Number.
Hope this helps
Jay