One of the features in Exchange Server is Outlook Web Access (OWA). This will allow a user to access his entire mailbox from a web browser. When logged into OWA, under options, there is a settings called Out of Office Assistant. The user also has the option to include a note which will serve as the body of the auto-reply message to the sender.
By default, auto-reply messages are only delivered to mailboxes within the exchange domain. If an outside user sends an email to the Exchange user with Out of Office Assistant enabled, the auto-reply will not be delivered. You need to click a couple of check boxes within the Exchange System Manager as detailed here.
When I did this, I had already enabled the Out of Office Assistant, and the auto-reply messages were not getting delivered. What I did was after enabling those 2 checkboxes and restarted the necessary services, I disabled (saved) and then re-enabled the Out of Office Assistant. That did the trick – the auto-reply was delivered.