I figured it out.

Here is the problem: if the fastcgi_cache_bypass directive is below the fastcgi_cache_key directive, you encounter this particular problem. Moving the fastcgi_cache_bypass directive above the fastcgi_cache_key directive solved the problem and now urls of any length are process correctly.

Sorry to bother you all!