I recently came across the following error message when one our users attempted to enable their out of office message in Outlook 2003:
Out of Office Fix
To fix this problem you will need to perform the following:
Shut down Outlook and open Windows Registry via Start->Run->regedit
Then find the following node:
Export the entry key listed under this node(just in case) and then Delete afterwards.
Relaunch Outlook and you should be able to set the Out of Office.