Here is more information on this issue...
Actually, the mailbox creation fails even directly in Exchange, and the cause is because of an incomplete UPN. This is easily corrected in ADUC on the account tab of the user account. Just pop the domain in the dropdown menu and save it. Once done, all is good again.
However, we see this happening whenever new accounts get created in Adaxes. Whenever the uniqueness script checks and must alter the username due to non-uniqueness, the account gets created without the UPN suffix for some reason.
I hope that helps troubleshoot the issue, as we do encounter this often.