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:
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?