Reno
The In Kraut
The scenes with Mrs Columbo off-camera are in later series though.
Early Columbo has a very different character to late Columbo. Early Columbo is, frankly, a scary character. He is relentless, apparently never sleeps and has a really dark streak to his character. It is entirely believable that this Columbo would make up a wife just as a device to get to the bad guy. Late Columbo is much more amiable.
I still think he actually gets married at some point around the seasons 3-5 mark and back-dating the wedding anniversary can be understood in the context that the early seasons take place 3-5 years before the year in which the episodes are aired.
I got the DVD box set of the entire Columbo not too long ago and I'm slowly working my way through it. There is no better comfort telly for me. In any case, he's only noticeably different in the pilot episode which was based on a stage play. From then on he's less harsh and the more familiar Columbo. I've only gotten to the start of season 2 so far, so can't remember how he develops form there.