Office 365 Reciepient Policies - Part 2

You may find that the default address policy does not apply automatically even though you have checked “Automatically Apply Email address policy” and “Allow Inheritable permissions” checked.  Take a look at your email address policies. Make sure the default policy has the highest priority. Check to see If you have any policies that were created pre-Exchange 2007 that were not converted and have not been applied in Exchange 2007. If these polices were applied to an object in Exchange 2000/2003 and not upgraded to 2007 then those objects will not get the new default address applied.

Delete the invalid policy and the force applying the policy with this one liner:

Get-mailbox -ResultSize Unlimited | set-mailbox -ApplyMandatoryProperties