I'm a little surprised the response wasn't to delist every Orange property from the Google search engine and block access to any Google property for any Orange customer. It seems to me that doing so would effectively render Orange's mobile broadband offerings dead globally, for the five minutes the discussion would last. Presumably someone at Google decided that such a strategy was too risky legally and/or in terms of poisoning relations with ISPs more generally.
Orange is also an highly trusted ISP in France, and (unlike Free) counts many corporations among its clients. Google probably would not risk alienating those clients by engaging in an open conflict with Orange.
All in all, I don't think any other French ISP would have been able to wrestle such a deal from Google.
According to Orange's CEO, Google just can't do without Orange in Africa - and that's likely to be true.
Sources (in French, sorry!):
http://frenchweb.fr/trafic-france-telecom-se-fait-remunerer-...
http://pro.clubic.com/entreprises/orange-france-telecom/actu...