I was under the impression that they only requested an ID and a mean of payment, but after verification you are right, a proof of residency is also required for postpaid plans.

If you know someone in France, you may ask them to make a "solemn declaration" that you live at their address; then you only need provide their own proof of residency (people living with their parents routinely do so).

Tourist and prepaid SIM cards are still exempted and, depending on your case, can prove quite interesting.