Got exactly the same problem over here.
Also exchane 5.5 with sp4, clients are nt with sp6a and email program Outlook 2000.
On every client the OOF is working allright, but you don't get any OOF reply's both internally and externally. Also checked the exchange option for sending OOF messages out to the internet, but that setting is also ok.
Just can't find the 'disable out of office assistant' option in exchange you are talking about.
Maeby you can help me with that??