For the past couple of months, one Exchange Server 2007 problem has plagued me. I had tried to install update rollup 3 in our organization. It worked fine on the front end servers, but certain services failed to start on the back ends. The Mail Submission, Mailbox Assistants, Replication Service, Search Indexer, and Service Host services all failed to "start in a timely manner." At that point, I punted and uninstalled the update.
A developer in our shop recently asked if I could install update rollup 3 to help with some performance issues he was experiencing. At first I thought to myself, "it's already installed," since most of our Windows updates are handled through Windows Server Update Services (WSUS).
My brain was blown when it wasn't installed, marked as not applicable in WSUS, and not present in Microsoft Update. That's when I found this little gem. Yes, that really reads, "Update rollups for Exchange 2007 are not detected for clustered mailbox servers by Microsoft Update." I was personall hurt by this. How could WSUS betray me? That's a different discussion.
Apparently I had blot my previous attempt to install update rollup 3 out of my mind, cause I blazed ahead and tried again. After installing the update on our two single copy mailbox cluster nodes, users could not send mail (a product of the Mail Submission service not running), messages would just queue in users' outboxes. I decided to install update rollup 4 to see if that would help things. It did not. Very frustrating.
After much searching and gnashing of teeth, I came across this very enlightening KB article. Once my incredulity and headache subsided, I went to work editing the config files for the Exchange services affected. This fixed my problem, services that had failed started, and mail started falowing again.
What was difficult about this is that it isn't a uniform problem. We keep our backend mailbox servers in a private non Internet routable address space. I have yet to figure out how to get proxy settings to apply to the Local System account, so these servers have not direct path to the Internet.
I would like send a shout out to this user's post on Experts Exchange. It really got the ball rolling. I don't know why my search queries didn't yield the actually Microsoft KB, but I am grateful I found this post. I also hope my post has helped others.
Cheers and good luck!

rollup
that rollup update had lots of problems. I believe update rollup 4 is out now so that should take care of things.
Wait...
You're actually praising experts-exchange? FAIL.
Yeah. I give credit where
Yeah. I give credit where credit is due. So if it's from experts-exchange then so be it.