A more structured allocation might be better, because you are very tight for available time slots. I think you need to run some monte-carlo simulations of your proposed system too (and check that you can first replicate your current failure timescale).
I'd suggest to incrementally slow-down any endpoint which is polling, but failing. Your steady-state should be within the available bandwidth, so the slowdown ought not to impact any/many active endpoints. If you do not back off, it only takes a couple of hundred endpoints to completely DOS your network.
You might also need to better characterise the connections, and the start-up state (assuming endpoints are static, but the router got rebooted). When all 60 connections are in use, does the next transmission kick off one of these, block several established connections, or need to wait longer for a slot to be freed up? What is the minimum number of pathologically timed connections to block the system (with worst case overlap of the 2 minute slots)? These ought to be reasonable easy to model in software.