Having been caught with an SBS 2011 server that had the Exchange Server 2010 Service Pack 3 Rollup 8 loaded, just before Microsoft withdrew that update. Apparently it caused connection problems with Outlook clients, although we had no reported issues.
Before you start make sure you've downloaded
Exchange 2010 Service Pack 3 and run it, so that its unpacked in a handy directory.
Going into Control Panel > Programs > View Installed Updates, you should see Exchange 2010 SP3 Rollup 7 and Rollup 8.
Select and uninstall Rollup 8. It takes a while to complete but will prompt for the location of msexchange.msi. This is actually the original SP3 installer, not anything to do with RU7 which is what you'd expect. So when it prompts, browse to the SP3 directory mentioned above, where you already unpacked the files, and choose that msi file.
The RU8 will uninstall and appear to leave RU7 on the updates list, however in reality your Exchange server is now all the way back at SP3 with no Rollups at all.
Reinstall
Exchange 2010 SP3 RU7 to bring it back up to date - and wait for MS to reissue RU8.
Bad week for faulty updates!