Nagle, much of the issues you're talking about with bad middleboxes is about signaling or optics into their status. We've had a standard for some years to deal with this (ECN). Why don't you think ECN is deployed at all? It seems to me it would be beneficial for all parties.
An overloaded middle box can do two basic things - drop packets, or reorder them. Many middle boxes do too much dropping and not enough reordering. Random Early Drop was probably a mistake. It's easy to implement, and beats dropping from either the tail or the head of a dumb queue. But that's its only virtue.
Any packet you drop eventually has to be resent. Packet dropping should be rare. Again, each flow should be allowed at least one packet in flight. This keeps the connection moving forward, and it means the endpoints can measure round-trip time and bandwidth, which should be reasonably stable because the algorithm is deterministic.
If you have so many flows that you can't handle one packet in flight per flow, you're so badly overloaded that no congestion management strategy will work.
Fair queuing is about dropping the newest packet on the flow with the longest queue. Thus, each flow competes with itself, and over-sending penalizes itself.
We really need to get home router/modems, cable headends, and outgoing routers just before the air link for mobile fixed. Those are the big choke points. You can't fix this from the end points alone.
ECN isn't a solution so much as it is an optional side-effect of routers deploying AQM—the real solution. Widespread deployment of AQM depends on having an algorithm that is both highly effective and requires no tuning or configuration. ECN deployment further requires being confident that broken routers won't cause problems and making a decision of where to put the threshold for marking relative to the threshold for dropping. You want there to be an incentive for endpoints to negotiate ECN, but you don't want there to be too much incentive for endpoints to declare ECN capability and then not respond to marking.