net start esperará que o serviço termine de começar antes de retornar, portanto, se o arquivo de lote for movido antes que o serviço termine, o problema é que o serviço relata falsamente quando é iniciado, ou demora o comando vezes fora.
Idealmente, o serviço deve ser corrigido para não reportar que tenha terminado de começar até que tenha terminado de iniciar. Você também pode fazer com que o serviço exiba um arquivo de estado ou algo para indicar que ele foi concluído e que seu arquivo de lote espere que ele apareça antes de prosseguir. Ou você pode criar um loop para verificar continuamente o status do serviço com "net start" ou "sc query" até que ele seja exibido como "Em execução", se os tempos limite forem o problema.
[Editar]
O que Karan disse.