MS Support Case resolved.

In the end, the resolution was a simple as bypassing the proxy server (WebMarshal), and everything sprung to life! MS Support were fantastic.

Problem Description:
You are unable to active Out of Office in Outlook 2007 for mailboxes that are resident on an SBS 2008 server.

Resolution:

Change the group policy by allowing internal network traffic towards your SBS server to bypass the proxy server.

Reference:

Overview of the Autodiscover Service
http://technet.microsoft.com/en-us/library/bb124251(EXCHG.80).aspx

Troubleshooting Autodiscover Connectivity for Outlook 2007
http://technet.microsoft.com/en-us/library/bb397225(EXCHG.80).aspx

Using WinHTTP Tools
http://msdn.microsoft.com/en-us/library/aa384084(v=VS.85).aspx