Primeiro, é importante ter em mente: Se bem me lembro, o cliente da política de grupo determina a "disponibilidade da rede" por meio de uma conexão bem-sucedida com o controlador de domínio, não apenas pelo cliente que possui uma conexão de rede. Você pode realmente ter uma conexão de rede que é inicializada em tempo hábil, mas um controlador de domínio de resposta lenta ainda pode causar o problema de "aguardar por rede". Isso pode explicar por que clientes em domínios diferentes não estão enfrentando o problema. Você pode querer verificar o log de eventos em seus controladores de domínio. Como Evan disse, um analisador de protocolo mostrará qual lado está causando o atraso.
Agora, para alguns conselhos de curto prazo que não abordam o problema raiz, mas que podem tirar temporariamente os usuários:
Fora de um controlador de domínio, o processamento da Diretiva de Grupo deve ser executado de forma assíncrona, a menos que você tenha informado especificamente o contrário, seja por meio de uma configuração de GP ou manualmente com o sinalizador / sync. No modo assíncrono, o processamento de diretivas não deve sustentar o processo de inicialização ou logon. Você pode querer verificar se, por acaso, habilitou a política "Sempre esperar pela rede na inicialização e no logon do computador". Está localizado em Configuração do Computador > Modelos Administrativos > Sistema > Logon Tente executar o RSoP no cliente e veja se ele é ativado - se estiver, desative-o. Você também pode querer dar uma olhada na política "Tempo de espera do processamento da política de inicialização" no mesmo local.
Isso não explica por que a rede não é inicializada em tempo hábil, mas talvez pelo menos tire os usuários de suas costas nesse meio tempo. O processamento assíncrono espera um pouco para tentar entrar em contato com o controlador de domínio para obter a lista de políticas, mas não deve esperar mais do que alguns segundos.