Oh well, "went" back to my operator, but I think they just are so selfconvinced the problem is not theirs, so they do not even investigate. Must be really weird bug/failure, that two otherwise working SIM-cards from the same network-operatorA do "not register", but with a network-operatorB's SIM-card and network-operatorC's SIM-card the device works normally and fine.

I guess I just change operator soon to get the problem fixed.