I create AD Users and Mailboxes from servers via PowerShell script from a remote machine.

It worked fine and all of a sudden it takes anywhere between 10 and 20 minutes for the mailbox to create.

I logged into the remote powershell script machine, opened PowerShell ISE and tested with the following scripts, with Verbose, and this was the result:

• Add-PSSnapin -Name Microsoft.Exchange.Management.PowerShell.E2010
• Enable-Mailbox -Identity 'DOMAIN/OU/OU/testcreateUser' -Alias 'testcreateUser' -Database 'Database1'-Verbose 

Everything runs fine up to this point, and hangs for 10 minutes:

VERBOSE: [09:07:34.120 GMT] Enable-Mailbox : [Microsoft Cmdlet Extension Agent] Read Email Address Policy for organization "" from domain controller xxx.

VERBOSE: [09:07:34.151 GMT] Enable-Mailbox : [Microsoft Cmdlet Extension Agent] Found Email Address Policy "Default Policy".

VERBOSE: [09:16:12.543 GMT] Enable-Mailbox : [Microsoft Cmdlet Extension Agent] Add Primary Email Address X400:C=xxxxx

Any idea why it hangs at the Default Policy?

Check if there are any non-SMTP email addresses listed in the Email Address Policy.  If there is, then it might be trying to find a server that has that proxyagent.dll file that is associated with the address extension.  This is common when there are different versions of Exchange installed in the environment.

Also, use the -domaincontroller switch with your enable-mailbox cmd and point to a DC local to the Exchange server that you are connecting to.