In a new Exchange 2010 environment (green field) that was running for two months it turned out that I was not able to create new mailboxes using the Exchange Management Console or the Exchange Management Shell. However, when I created new users through Active Directory Users and Computers and then Mailbox Enable the user it worked fine!

The following error showed up in the Exchange Management Shell:

[PS] C:\Windows\system32>New-Mailbox -Name 'JWT' -Alias 'JWT' -OrganizationalUnit 'contoso.com/Bedrijf/Productie/Gebruikers/Groepspostbussen' -UserPrincipalName 'JWT@Contoso.com' -SamAccountName 'JWT' -FirstName '' -Initials '' -LastName 'JWT' -ResetPasswordOnNextLogon $false
WARNING: A script or application on the MX-S001.Contoso.com remote computer is sending a Prompt request. When prompted, enter sensitive information like your credentials or password only if you trust the remote computer and the application or script requesting it.

cmdlet New-Mailbox at command pipeline position 1
Supply values for the following parameters:
Password: *********
Active Directory operation failed on DC-S001.Contoso.com. This error is not retriable. Additional information:
Access is denied.
Active directory response: 00000005: SecErr: DSID-031A1190, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0
+ CategoryInfo          : NotSpecified: (0:Int32) [New-Mailbox], ADOperationException
+ FullyQualifiedErrorId : F1DEA2E9,Microsoft.Exchange.Management.RecipientTasks.NewMailbox

[PS] C:\Windows\system32>

Since it was possible to create new users using ADUC it must be something with the impersonation, i.e. the Exchange Trusted Subsystem.

Using the /Verbose option in the New-Mailbox cmdlet shows a lot of additional information of what’s going on under the hood. Everything went well, except for something during the actual creation. Unfortunately nothing special was logged in eventlog, except that the cmdlet was failing. Duh!

After some more digging it turned out that it failed during the reset password function, a permission that was not available on the Exchange Trusted Subsystem account. The reason why it was not set is not really clear, but most likely it is a side effect of domain controller security hardening effort. Using Active Directory Users and Computers select the domain and select its properties. On the Security tab select the Exchange Trusted Subsystem account and allow the Unexpire Passwordoption.

Now the New-Mailbox cmdlet is working as expected.

Special thanks to Jaap K. and Frank L. at ‘contoso.com’ for their input in troubleshooting this issue