浮気？彼を信じるべきか。。。

嫉妬は理屈じゃないので難しいですね…。
年賀状は、単に主さんにいやな思いをさせたくなくて隠していたという可能性もあると思います。
私なら、その相手に私の目の前で「もう連絡は取らない」と電話かメールをしてもらい、彼女の連絡先を全て消去してもらいます。
実際には住所は分かっている訳だし、SNSなどもあるし完全に消去というのは難しいのは分かっていますが、その時の態度を観察して、誠意があるかどうか確かめます。
ただ、初回から時間が経ってしまっているので彼の方も「なぜ決着したのにまた蒸し返す」と反発してしまうかもしれません。
「貴方を責めたいのではなく、不安なので安心させてほしい」と説明してみて下さい。