I spoke to Microsoft Germany about this. Our problem was that the update rollup 4 would always stop with event id 1024 (error code 1603).
They recommended I stop all the Microsoft Exchange services, IISadmin and World Wide Web Publishing. Then change all the service startup types to manual (not automatic). Then install the update from an elevated command prompt. Then restart all the services and change back the startup types.
This worked for me.
As feedback for Microsoft I would say these sort of issues really should be caught before release. For my company Exchange server downtime is hard to organize and not a fun project when you read the problems people have had with this update! With Exchange 2007 we had no problems with any "update rollups" but with Exchange 2010 the team should really look at resolving all issues before releasing them.
Cheers,
Joe