What version of Outlook do you use? Outlook 2003 does not have an option for OOF messages to be sent to external senders. Did you set up the OOF in Outlook Web or Outlook? If you set it up in OWA and then look at it Outlook 2003, just viewing it in Outlook 2003 will over-write whatever you did in OWA.
<a href=”http://msexchangeteam.com/archive/2007/04/04/437544.aspx”>Read this</a>
Please see the Blog on Microsoft. Mr Song has an excellent troubleshooting series. http://social.technet.microsoft.com/Forums/en-US/exchangesvradmin/thread/8860c9d4-3083-4862-9021-48ca0ee10456