Are you also using Word 2003? Both programs need to be the same version. Do you have AVG anti virus installed? If you do disable it and then try to send or reply to an email again.
You said you did a detect and repair – you said that failed. What was the error message given?
If all else fails uninstall office 2003 completely. Reboot. And install it clean.
Of course backing up your PST file before you uninstall.
Outlook and Word are both running 2003. We don’t have AVG installed. I meant that Detect and Repair failed to fix the problem, I apologize for the confusion there. I uninstalled 2003 and reinstalled and we are still having the same problems. Office 2003 has also been updated to SP3 just it case it might have helped, but no luck.