Ok, so the factory reset actually wipes firmware updates as well. After installing firmware update and reinstalling/readding Exchange account I'm now able to sync contacts, e-mails and calendar just fine. Great.