Apologies if this is a duplicate, but none of the questions I've found so far seem to answer this specific question.
I have a SharePoint site where no users (or almost no users) can create alerts because they get the message:
The following users do not have e-mail addresses specified: DOMAIN.COM\username. Alerts have been created successfully but these users will not receive e-mail notifications until valid e-mail addresses have been provided
All of these users are domain users, and all have Exchange mailboxes in the same domain.