if you opt to take airline miles (instead of their new award program points where they give you a golf putter after 5 rentals or so), you can still get 500 miles for a non-government rate. hertz was the cheapest rate i found on the last two trips i took (iad and atl), but they were both weekend rentals with a 10% internet discount (www.hertz.com).

don't know how long they'll keep awarding airline miles, but as the previous post noted, the airlines are starting to realize that 500 miles for a $25 rental doesn't make good corporate sense (to them at least... i think it's great!!).