У меня несколько доменов. Часть пользователей получают почту, а часть нет.

Откройте закладку Accepted domains в Exchange Management Console -> Organization configuration -> Hub Transport

Добавьте Ваши внешние домены в данный список.