This was for Exchange 2007.
On the event viewer I see tons of warnings related to .NET misconfigurations right after the Windows Update. Also my phone stopped getting emails at that time.
Uninstalling the windows update solved the problem.
Thank you Microsoft!!!