First make sure that your Outlook clients are using the Mailbox located on the server as message delivery and not using Personal folders. This is easily checked in the Outlook Profile under the delivery tab.
If the client is using Personal Folders for delivery and not the server, then you will not have the option of allowing for server side rules.
If the clients in question are laptops, then use the Offline Store capability this way they can still utilize server side rules.
What you are describing is the Out of Office feature. Each of the clients should have this capability, just make sure that they generate the Out of Office while connected directly to the server. This way its guaranteed that their server inboxes have been updated.
Also you may want to check your IMC/IMS (SMTP Server) to determine if you are allowing OOF messages to the Internet.