Interesting. Just this week I had to investigate the exact same issue at my job. One user (of course it was the CEO...) had accumulated so many cookies that on some pages of our website he ran into the HTTP request header limit and would only get a 500 error page.
One risk factor is using JavaScript based third party services that use cookies with your host name. In our case, it was Optimizely that was storing pretty significant amounts of data in cookies. Not really sure how to tackle this issue.
We had the same issue with Optimizely cookies. They serialize the experiment data as a json blob, which grows with more experiments, and store it in a cookie. What a pain to debug as it wasn't consistent for every user.
Forgot to mention that we're using Akamai, and it's actually Akamai's servers that are hitting the limit. We'll see if we'll be able to convince them to bump up the limit. I have a hunch that there might be some resistance because of performance implications (I'm not an operations guy, my knowledge of how web servers work internally is limited). On the other hand, it seemed to intermittently work, so there may be some servers in their farm that are configured differently. Or it could have been due to fluctuations in the header length because of different query string lengths and cookie changes.
One risk factor is using JavaScript based third party services that use cookies with your host name. In our case, it was Optimizely that was storing pretty significant amounts of data in cookies. Not really sure how to tackle this issue.