This is an oldie. Surprised I did not post this when I first encountered Exchange services not starting in 2008. May be I was too engrossed in this.
Microsoft in their infinite wisdom has decided Exchange 2007 services will be signed via certificates. The Exchange Services on start up will validate the certificate chain. If the Exchange server has a clear path to the Internet, everything is fine. Otherwise the certificates are not validated and Exchange services don’t start. Actually I have encountered those services don’t start even if you don’t have an Internet proxy installed. May be the services were unable to authenticate with the proxy service.