Have you made sure that the users emails are actually imported?
If so, are there any differences between working an non-working addresses (domain, funny characters, etc)?
If not, does the same apply when you update a user manually by adding the email address on the user profile?
.b
http://furuknap.blogspot.com/My SharePoint blog with articles, reviews, and code samples.
Anonymized questions and answers may be posted to my blog.