I don't have direct experience with your situation.

The only time I lost an Avis key, I knew I lost it. I was in France at the time and had done a day trip out of CDG to NTE. The key was definitely in the inner "key pocket" of my suit coat when I left CDG in the morning. When I returned to CDG that night, the key was not longer there.

Avis-CDG made me walk with them back to short-term parking to see the car (and a couple of things I had left in there). Then we walked back to the counter, they found another key, and charged me a ~eur100 fee.