If you are experiencing issue with external users not getting the “Out of Office” notification even though you have added the “Out of Office” message on their mailbox with Outlook, then most likely this is because you are using an older version of Outlook. If you are using Outlook 2003, you will only be able to setup the “Out of Office” for Internal users (Users Inside your Organization only). To send “Out of Office” to external users, you will need to use OWA, web mail.
Outlook 2007 and Outlook 2010 have the “Outside My Organization” tab option when using the “Out of Office Assistance”.
Click on the following link to view the instructions