the tests you have done seem to indicate that it is indeed a SIM issue. The next step : read this SIM card through a SIM reader (I recall TEMS Investigation provide such functionality, doesn’t it ?)
you can read the PLMN settings of the SIM, I guess…
Both sets of SIM were inserted in the same mobile phone ? The question is whether the mobile phone could be the problem here.