Recently, I has a user who was unable to set an out of office reply. They were able to set it through OWA, but it seemed odd. The fix ended up being a simple reconfiguration.
Once in the Advanced settings, go to the Connections tab and open the Exchange Proxy Settings.
Once there, enter the web address for your domain, for example OWA.DOMAIN.COM or MAIL.DOMAIN.COM. Click the two check boxes for On fast networks… and On slow networks… and change the Proxy authentication settings to Basic. Now these settings may be different from your network settings, but this is should be a step in the right direction.