We don't use exchange where I work, we use Google Apps.
Figured out the issue though, we recently put some users on Kaspersky 8 from 6, which cause compatibility issues with the outlook plugin. Reverted them back to Kaspersky 6 and it's working fine.