So do the following
1. Open the Vault Admin Console
2. Expand out Your Site -> Targets -> Exchange
3. Right Click "Exchange" and select "Display Policies Assigned To Mailboxes"
4. Enter a user that you know is affected by this issue
5. Note down the Desktop Policy and close the window
6. Expand out Policies -> Exchange -> Desktop
7. Go to the properties of the users Desktop Policy
8. Go to the "Advanced" tab and on the drop down , selected "Vault Cache"
9. Look at the very top option "Archive Explorer Connection Mode"
10. Make sure its set to "Respect Connection" then press Apply
11. Go to the users Archiving Task and go to the properties of the task
12. Go to the Synchronization tab and choose "Selected Mailboxes" and press the Synchronize button
13. Find the user you found at the beginning and synchronize the mailbox
14. After the mailbox succesfully synchronizes, close and restart their outlook and try again