For example, they could make it illegal for a company to make available the private communications of French residents to any third party, explicitly sovereign intelligence agencies.
I think this would put Facebook, Google and such into a catch 22 and pressure for an agreement would come from companies like these. Imagine Facebook being prosecuted in France for complying with an NSA directive. It would be especially effective if done as part of a big case/effort where sovereign intelligence agencies included rivalrous countries (Russia, US, China) that don't like to be compared to one another.