They say that the problem was the number of items in one queue. If this is the issue, and they have a way to handle a large number of small full queues but not

They say that the problem was the number of items in one queue. If this is the issue, and they have a way to handle a large number of small full queues but not a single huge one, what comes to mind is linking some "virtual queues" so that a queue is stored in many small queues, stored on different servers. Instering an item would put it in the first queue until that reaches the limit, then switch to a new one, on another server.