Although all parameters for this cmdlet are listed in this topic, you may not have access to some parameters if they're not included in the permissions assigned to you.
To see what permissions you need, see the "Address lists" entry in the Email address and address book permissions topic.
By default in Exchange Online, the Address List role isn’t assigned to any role groups.
To use any cmdlets that require the Address List role, you need to add the role to a role group.
I'm having an issue with Exchange 2010 and Outlook 2010. This problem started after we flattened our domain. We migrated all the users from the the sub to the top using the ADMT and then we took down sub. To be sure, does OWA (which uses live information) reflect the GAL correctly? The first thing you should do is on a test workstation, is delete the *files.
Essentially, the issue is the GAL is not updating in Outlook. I looked at the recipient filter of the GAL, it's below for reference: (Alias -ne $null -and (Object Class -eq 'user' -or Object Class -eq 'contact' –or Object Class -eq 'ms Exch System Mailbox' -or Object Class –eq 'ms Exch Dynamic Distribution List' -or Object Class -eq 'group' -or Object Class –eq 'public Folder')) The next thing I'm going to try is creating a new GAL and making it the default, if necessary. That will force Outlook to download a complete GAL. If so, it is probably that the incremental update files haven't updated correctly.
I ran the commands you recommended and tried it about 4 hours after that. As another way to troubleshoot the problem, I created a new profile for Outlook.