Outlook 2007 Out of Office (OoO or OOF) in legacy mode

We have a clustered E2K7 (SP1 + latest rollup) envrionment with Outlook 2007
SP1 and some of our clients insist on using the legacy mode Out of Office,
but others work fine with the new stuff.

We have used the latest Outlook rollup/hotfix (Feb 24th I think) with no
improvement. The problem seems to occur at remote sites (our exchange
cluster is located at HQ) and can be "fixed" by enabling outlook client
encryption. Trouble is we need this to be disabled due to our WAN
accelerator not being able to optomize encrypted data.

I cannot find anyone referecing a similar issue, or any connection between
encryption between outlook and exchange and OOF in legacy mode.

We have multiple sites defined, but there is no special setup from site to
site, our autodiscovery is vanilla.. The Outlook 2007 E-mail
Autoconfiguration test succeeds and has no errors.

If anyone know the solution, please let me know.