Muito estranho. Eu acho que há algo estranho acontecendo aqui. Se você tiver o TechNet ou o MSDN, eu gravaria um caso com o MS para resolver isso. Pode haver alguma estranheza com o ambiente ou com a instalação padrão do Windows ou do SQL Server que está causando isso.
Uma coisa que você pode fazer é definir um item do Agendador de Tarefas conforme mencionado acima para iniciá-lo.
Se você definir uma reinicialização do serviço na falha, isso funcionará?