Você está no caminho certo com a abordagem baseada em cookies, mas a verificação inicial precisa ser feita usando um processo muito mais barato que um thread Apache / PHP. Eu sugiro um proxy nginx na frente do seu host que obriga a redirecionar e definir um cookie. Do que apenas as solicitações com o cookie apropriado são permitidas até mesmo para o seu host PHP.
E enquanto você estiver configurando um proxy, esse software relativamente novo de detecção de bot é bastante impressionante:
Também sugiro que a apresentação de DDoS seja vinculada a essa página:
Ele cobre os conceitos anti-DDoS em geral e descreve por que eles escreveram o Roboo.