Exchange 2010 SP3 Rollup 8 has been updated to v2 and its fixed!
Microsoft has re-released Rollup 8 for Exchange 2010 SP3 after last weeks cockup!
Its not on Windows Update yet, but can be downloaded here http://www.microsoft.com/en-us/download/details.aspx?id=45225 (KB2986475)
The best part is that it actually works! Looking at the behaviour it appears the Rollup broke the behaviour of the RPC protocol in Exchange 2010 when it communicated with Outlook clients that were online.
The patch will usually require a reboot for Mailbox Servers, but Client Access Server are quite happy to carry on as before.
Just a note for those who are operating DAG mailbox servers, remember to shift the mailboxes to the other mailbox servers before applying the update otherwise your users get cut off because the rollup doesn't handle this process.