Talvez o banco de dados padrão para o login da conta de serviço tenha um tempo significativo para inicializar (porque é grande ou tem algum outro problema?). Para testar isso, você pode alterar o banco de dados padrão desse login para tempdb.
ALTER LOGIN [domain\user] WITH DEFAULT_DATABASE = tempdb;
Você também pode considerar adicionar TRY/CATCH
de tratamento de erros ou aguardar a lógica em seu serviço para que não falhe completamente devido a uma incapacidade momentânea de se conectar (especialmente durante a inicialização).