This rather points to a problem with the Access Point Names for your carrier.
How did the problem arise, what changed or was it a new install?
The sort of thing that has cropped up for other users is seen in threads with hashtag apn.
Do you see Emergency calls only?
If yes your carrier will know your phone is there but disconnected. An easy first thing to do is to ask the carrier if they will perform an Over the Air (OTA) APN reset.
This made me think of a simple solution: If neither SIM nor phone are the actual problem, but the connection itself, it should help switching the SIM with another, non SIM-locked, phone for forcing all devices, SIM cards and carriers to build a new connection. This worked.
We switched back and it still worked, as if there had never been any problem.