Microsoft Exchange 2003 default settings do not allow out of office replies to leave the internal domain. A lot of users want this on if they deal with a lot of external clients.
Options to Change:
Using the Exchange System Manager, open Global Settings >> Internet Message Formats, right click “default” on the right hand panel. Select Properties >> Advanced. Check the “allow out of office responses” box, and “allow automatic replies” Click apply and then okay.
Restart SMTP Service
Go to Start>>Programs>>Administrative Tools >>Services>>Right click on the Simple Mail Transport Protocol and Click Restart
Your external senders should now get the out of office messages, keep in mind they will only get once per time the out of office is on, this is done for obvious reasons to prevent mail loops, etc.