We took over support for a new SBS2011 server installed in July 2012. First restart and we had Exch 2010 services Client Access, exsearch.exe and other auto start services not started.
This was exact symptoms.
We worked around this by stopping Exch services and setting RPC Locator Service to automatic and Started. Then started Exch services.
So the question is, will this be “good enough” for Exchange to start properly or do we need to put in a “boot delay” or change dependencies like shown in KB above?