I would give the writers a pass on the phone records.

Back then, there were only phone records of long-distance calls for which there was a fee; Even within the same area-code a call could be considered "long-distance", but not as costly as outside the area-code.

The brothers in "Double shock" could live far enough apart to be a long distance call.

In "Crucial Game", the phone-booth to house call would not have been long-distance and would not have been logged. As for "the phone company can't verify that", the lack of a logged toll gives Columbo sus.picion but of course you can't PROVE he didn't call just because the call wasn't logged. In a court of law you could always just blame it on a phone-company error, and that's plenty of reasonable doubt.