Ok so this is through your work, so you are obviously not the only one using outlook right ?
Anyone else having this issue ?
Have you created a new outlook profile ?
Have you re-entered your username/exch server in the properties ?
Are you able to verify that exchange is able to see you ?