That's definitely unpleasant.
It's been my experience that Hertz indeed doesn't remove cancelled reservations from their system properly, or at least doesn't do so for reservations cancelled X days in advance. I've had an agent at Hertz HLE pull up wrong reservation that was for $20 more (which I cancelled beforehand, just like you). I noticed it right away and they fixed it. Based on that, I wouldn't attribute this to someone trying to screw you over, but rather to an honest mistake.
PS. Please don't complain about Ultimate Choice at airports. Try going to an off-airport location with 2 cars to choose from (or none to choose from) and you'll run right back to the airport.