Um navegador pode enviar cookies que são genéricos para o seu domínio (por exemplo, para example.com e também para webapp.example.com) - pode ser que esses cookies tenham sido definidos por um site não relacionado cujo nome de domínio termine com o mesmo TLD.
Os proxies HTTP podem adicionar seus próprios cabeçalhos HTTP a respostas e solicitações. Eles também podem alterar os cabeçalhos HTTP existentes.
Qualquer um deles pode aumentar o tamanho do cabeçalho HTTP.
A melhor maneira de descobrir o que está acontecendo é registrar a solicitação HTTP. Isso pode ser feito usando um sniffer de pacotes como o Wireshark ou o tcpdump no PC do usuário ou no servidor - eu filtraria pelo endereço IP da outra extremidade.
Obviamente, se você puder minimizar o número e o tamanho de seus cookies, isso ajudará. Idealmente, os cookies apenas conteriam um ID de referência para informações de estado armazenadas no servidor.