guess that's because of the encoding for it...
Can you validate the exact error code being thrown:
404.13 | Content Length Too Large
404.14 | URL Too Long
404.15 | Query String Too Long
I assume you'll get the last one the 404.15
You could check the following web.config update:
<system.webServer>
<security>
<requestFiltering>
<requestLimits maxQueryString="xxxx"/>
</requestFiltering>
</security>
</system.webServer>
Do note that some older browsers might not work with long urls... believe 2048 is a unwritten rule for the highest cross-browser length limit for a complete URL.
Apart from that, wouldn't it make more sense to just limit the max length client side?