It sounds more like the certificate last downloaded by Outlook has become invalid. Generally, if you launch Outlook and it thinks it needs an updated cert, it will bring up a confirmation window.
It may also be a problem with the configuration of the actual exchange server. Are you able to send/receive manually?