I'll bet that it was Budget. I have had the IDENTICAL thing happen to me there, but they refused to correct the situation. After a number of conversations with the airport staff, the city office and their national office, I gave up and conceded the $20.

They also have a nice racket going on for charging for tiny dings and scratches. Check out my rantings on the Budget board for that. Inch-long luggage scratch on back bumper: $500.

As for Hertz, I have never had any problems with them. I am just not willing to pay the extra $20-50 a day that they usually charge over Budget/Dollar/Alamo.