Yeah, Trevor - all that you mentioned my firewall can do... Along with IDS, IPS, etc., etc. Why? Because we choose our firewalls well (no Cisco ASs-A). The revolution in WAN is actually next-gen firewalls - pick well and you don't have to rely on bunch of crew-ups otherwise known as "service providers".
Simple policy worked for us - get the minimal, most generic service ISP (inet with ethernet hand-off, p2p ethernet, etc.), then integrate it into your infrastructure properly.
And any time we got away from it - SP finger pointing every time there is a problem.