I have experienced this issue in my latest OCS deployments now and want to share this information. This issue happens after installing the january cumulative updates server-side. This issue is not related to the CryptoAPI issue described here: http://msunified.net/2009/10/14/for-now-hold-off-on-installing-kb-974571-on-ocs-2007-r2-servers-and-possibly-r1/

The Problem 

• I have experienced this issue on Enterprise Front End servers and Mediation servers
• The after reboot it takes for ages to be able to connect through RDP, ping works fine
• When you finally log in you find that the Front End or Mediation service has not started
• When you start the services everything works fine

The Solution 

• Set the services below to automatic start
  • [Winmgmt] – Windows Management Instrumentation
  • [Keyiso] – CNG Key Isolation
  • [WMIapsrv] – WMI Performance Server
  • [Rasman] – Remote Access Connection Manager
• On the Enterprise Front End server set the rtcsvr dependent on the above services
  • Open Command Prompt as administrator and run the below command
  • sc config rtcsrv depend= WinMgmt/KeyIso/WmiApsrv/rasman 
• On the Mediation server set the rtcmedsrv dependent on the above services
  • Open Command Prompt as administrator and run the below command
  • sc config rtcmedsrv depend= WinMgmt/KeyIso/WmiApsrv/rasman 

I have seen similiar problems talked about in the below blogposts:
by Mino – The UC Guy: http://theucguy.wordpress.com/2009/05/13/ocs-2007-r2-server-loses-network-connection-on-server-startup/
by Aaron Tiensivu: http://blog.tiensivu.com/aaron/archives/1909-OCS-2007-R2-services-hang-at-Starting-on-reboot-with-Server-2008.html