Interesting point about the gum in "Agenda For Murder." Columbo's real evidence is the piece of cheese, which apparently coupled with the other circumstantial evidence enables him to get a court order for a mold of Oscar Finch's teeth.
It is interesting that despite the search for the gum being illegal, it gives Columbo a head start to the final clue.