Even Linux is not magic, but..

Network was broken by design and the requirements where conflicting.

However, following tricks helped:
 * Removal of Cisco cruft
 * 5 additional Linux machines
Iptables MSS clamp 
Agressive Queuecontrol
Shaping (CBQ+TBF)
Iptables driven MRTG
 * Adjustment of expectations