O Windows está efetuando login no servidor para ver se o comando desejado está nessa pasta. Depois da primeira vez, ele já está conectado. Temos o mesmo problema ao abrir documentos e pastas no servidor todos os dias.
Você pode ser capaz de acelerar (no Windows) executando o seguinte comando durante o login:
Net Use \ServerName
O comando levará um minuto para ser processado, mas pode acontecer como uma tarefa em segundo plano que o usuário não notará. No entanto, não sei se isso causará problemas com "muitas conexões" no seu caso.