Did a bit of troubleshooting and found a workaround (for Windows Mobile at least) at
Windows Mobile Emulator images and Exchange 2007 - The Windows Phone Guy
As I don't like complex patches, I tried changing those keys one by one and finally just changing the following key worked in my case:
HKEY_LOCAL_MACHINE\Security\Policies\Policies
"00001017"=dword:000000b4 hex (= 180 decimal)
Googling the key didn't bring me much insight, though it might have something to do with security signatures. Having said that, this setting worked for me, but I can imagine other Exchange environments enforcing other policies that your device needs to support. So it'd be trial and error, changing values in the HKEY_LOCAL_MACHINE\Security\Policies\Policies key.
