After posting my message, I found out the following information and thought that I would share this with you all (just hope that it isn't outdated info on the web or that it is about to change like everybody elses).. Still looking for other ones as well:

NorthWest Airlines: http://www.nwa.com/freqfly/earn/carre.shtml
Earn 500 miles for leisure rentals with Alamo or National in conjunction with a flight. Earn 500 with Dollar leisure rentals without a flight. Also, earn 500 miles for Budget if rental 2 days or longer in conjunction with a flight.

note: USAirways gives 250 miles with rentals from Alamo and National.
see: http://www.usairways.com/dividend/earn/rentcar.htm