This issue affects both NuGet and MyGet (as we reuse the NuGet API). We recieve reports from certain projects that are consuming A LOT of packages that they cannot call GetUpdates because the request's querystring is longer than the allowed limit. We already increased it on our side to something like 8K, which fixed 404 errors on our side, but the NuGet Gallery still has this issue.
For an example request URL (modified because of confidentiality), see below:
... etc etc
Increasing the querystring length limitation is a short term solution, but maybe a more long term solution is required, e.g. POSTing the pkg information