Try doing a dearch on the outlook 2003 machine for any .ost files and delete them. You have to search in hidden folders so make sure you enable the ability to view hidden folders first.
If you still get the error, go into the mail profile via the mail icon in the control panel and turn off cached mode. Try connecting again without cached mode and see if that will work. If it does, try turning cached mode back on and restarting outlook. That is, if you want to use the cached mode.