Don't forget to take a look at:
http://www.bonjourparis.com/directory/
AutoEurope.
It's known to have some fabulous promotions.
I have used AutoEurope a few times. The only thing is that the fare they post is without all the fees and taxes and theirs are much higher than what you see on the websites of the airlines. I am not sure how that works....
Also you have to double check about the frequent flier miles. I had an issue with them a couple of years ago and they ended up giving me a big credit as I didn't get my ff miles as they said I would and had done before.

