Products: MS Exchange 2003, Outlook 2003
The fix was an esoteric MS workaround involving a special Information Store (MS Exchange) tool.
Details on how to use the tool are here: http://hellomate.typepad.com/exchange/2003/10/when_oof_doesnt.html
and here: http://support.microsoft.com/kb/248709
The tool’s filename is mdbvu32.exe
Update 4/3/2007:
Note: *don’t forget you can double-click on the Rules and scroll down to see if they are an out of office rule or something else.