Clearing OWA and Outlook autocache

Anyone who has participated in migrations or transitions to Exchange has most likely encountered or has had to work around potential issues caused by the nickname cache. A “cache,” also known by its file extension, NK2 in older Outlook clients, is a convenience feature in Outlook and Outlook WebApp (OWA) which lets users pick recipients from a list of frequently-used recipients. This list is displayed when the end user types in the first few letters. 
The potential issue revolves around end users using those lists to send messages, as the list contains cached recipient information. Because this information is static, it may become invalid at some point. Thus, when users pick recipients when sending messages, they may be sending messages to non-existent recipients or invalid e-mail addresses, which create issues like non-delivery of e-mail.
In an earlier version of Outlook, this information was stored in local .NK2 files. In Outlook 2010 and up, this information is stored in your mailbox (AutoComplete Stream). Unfortunately, OWA utilizes its own cache mechanism while Outlook stores recipient information in other locations as well, like the ‘Suggested Contacts’ folder for example.
For the storage of static recipient information,  some migration scenarios organizations might wish to zap all or parts of that cached information at some point in the process. For that purpose I have written a script. Depending on your scenario, this may prevent NDR issues or users being instructed to clean those entries themselves at the cost of having them re-enter frequently used e-mail addresses once.
Before I get into details on script usage, I will first elaborate a bit on the various caching mechanisms.
AutoComplete Stream
The autocomplete stream contains information from previously used recipients when using Outlook. The list contains address information such as SMTP or LegacyDN addresses and is limited to 1,000 most-recently used entries. The information is stored in a so-called folder-associated information (FAI) table in your Inbox, which is a hidden folder. FAI entries can be inspected using utilities like MFCMAPI or EWS Editor, like in the example below where I opened the associated contents of an inbox using MFCMAPI.
The autocomplete stream is stored in the item of message class IPM.Configuration.Autocomplete. The entries themselves are stored in the property PR_ROAMING_BINARYSTREAM (pidTagRoamingBinary, tag 0x7C09000A) which, as the name implies, is in binary format.  However, you can inspect the information in a more comprehensible format using MFCMAPI. In MFCMAPI, open up the PR_ROAMING_BINARYSTREAM property of the  IPM.Configuration.Autocomplete item using the Smart View structure definition Nickname Cache.

Be advised that Outlook will only retrieve the autocomplete stream when addressing functionality, like when entering a recipient in the To section when composing an e-mail. Any updates to the autocomplete stream will not be written back to the FAI item immediately, but will be saved when Outlook is closed.  Because of this, Outlook has to be closed when making changes to the autocomplete stream otherwise Outlook may overwrite it with its version of the autocomplete stream.
Note that Outlook may cache autocomplete streams locally in %userprofile% under \AppData\Local\Microsoft\Outlook\RoamCache. The files are named Stream_Autocomplete*.dat, with only one .dat file per configured account. These files are used when running Outlook in Cached Mode and serve as a storage location  for updating the FAI item.
End users can reset the nickname cache from Outlook via File > Options > Mail > Send Messages using the button Empty Auto-Complete List, or through starting Outlook using the switch /CleanAutoCompleteCache.
Outlook WebApp AutoComplete
Like Outlook, Outlook WebApp (OWA) caches recently used recipient information. Unfortunately, it does not share this information with Outlook. OWA stores its autocomplete stream information in the FAI table of your mailbox root folder, in a User Configuration object of message class IPM.Configuration.OWA.AutocompleteCache. In the example below, I opened the associated contents of the root container of a mailbox using MFCMAPI.
The autocomplete stream is stored in the item of message class IPM.Configuration.OWA.AutocompleteCache, but when accessing User Configuration information through Exchange Web Services, you need to remove the IPM.Configuration prefix. The entries themselves are stored in the property PR_ROAMING_XMLSTREAM (pidTagRoamingXmlStream, tag 0x7c080102) which, as the name implies, is stored in XML format (in the example the stream does not contain any entries).

In OWA Light (not Premium), end users can reset the OWA nickname cache via Options > Messaging >  Clear Most Recent Recipients List.
Suggested Contacts
The Suggested Contacts folder is created by Outlook. It is an Address Book to which contact objects will be added for each recipient used to send messages to, but that are not present in your Contacts folder. Like ordinary address books, Suggested Contacts can be used as an additional address book for picking or searching recipients.
Note that unlike autocomplete, Suggested Contacts entries cannot be searched when typing the first few characters of a recipient.
Recipient Cache
The Recipient Cache folder was introduced with Exchange 2013. It is a non-visible, well-known folder that sits below the Contacts folder.

Unfortunately, the specific purpose of the Recipient Cache folder is not documented. It does however, contain cached recipient information.
Clean-AutoComplete script
The script is really straightforward. It requires Exchange 2010 or later and Exchange Web Services Managed API 1.2 (or later) which you can download here. Alternatively, you can copy the Microsoft.Exchange.WebServices.DLL with the script as it will also look for it in the current folder.
The script Clean-AutoComplete.ps1 has the following syntax:
Clear-AutoComplete.ps1 [-Mailbox] <String> [-Server <String>] [-Impersonation] [-Credentials <PSCredential>] [-Type <Array>]
Where:

• Mailbox is the name or e-mail address of the mailbox.
• Server is the name of the Client Access Server to access for Exchange Web Services. When omitted, the script will use AutoDiscover.
• Switch Impersonation specifies if impersonation will be used for mailbox access, otherwise the current user context will be used.
• Credentials specifies the user credentials to use.
• Type specifies what cached recipient information to clear. Options are Outlook  (Outlook AutoComplete stream), OWA (OWA Autocomplete stream), SuggestedContacts, RecipientCache or All. Default is Outlook,OWA.

So for example, suppose you want to clear the Autocomplete stream used by Outlook on a mailbox, you can use:
Clear-AutoComplete.ps1 -Mailbox Olrik -Type Outlook -Verbose 

To remove the Autocomplete stream used by OWA on your Office 365 account, you can use: 
Clear-AutoComplete.ps1 -Mailbox olrik@office365tenant.com –Credentials (Get-Credential) –Type OWA
You can download the script from my Technet Gallery here.