Quando você diz "domínios aleatórios" você quer dizer nomes de host, certo? Não endereços IP?
Se o primeiro, um nome de host é, pelo menos em teoria, completamente desconectado do endereço IP real do servidor do ponto de vista do servidor. Cada (bem, quase todo) pedido HTTP terá um cabeçalho HTTP chamado 'Host', é muito fácil simular ou "fingir". Tome o seguinte comando
curl -H "Host: serverfault.com" http://www.google.com/
(Ignore a saída)
Esse comando faz com que os servidores do Google respondam a uma solicitação de "serverfault.com" como se fosse um host virtual normal, que no caso do Google parece estar apontando para um arquivo que redireciona para o site principal do Google. / p>
Simplificando, não há como "bloquear" essas solicitações sem fazer com que seu firewall analise cada solicitação e isso abre um outro mundo de problemas. Uma resposta 404 ou 403 está correta, 404 significa que o recurso não existe no servidor, embora, normalmente, isso corresponda a um arquivo, ele pode referir-se a um site inteiro também.
O seu servidor optar por responder ou não, é baseado (simplista) apenas no endereço IP de destino, não no nome do host. No momento em que o servidor começa a ler o nome do host, já está estabelecida uma conexão. Sim, você poderia obtê-lo apenas para soltar a conexão, mas responder com um 404 é uma opção muito melhor porque informa oficialmente ao cliente que o recurso não existe.