Similar experience on my iPhone 14 Pro Max, with iOS 16.4.1...
When using iPhone 14 Pro Max (without WI-FI service, e.g. highway, supermarket, any where without WI-FI), my device (iPhone 14 Pro Max) ran into connection problems:
1. Safari "Fails" to respond to "search", or "Fails" to load the page from know URL.
Its status shows the device is with signal (level at 4 bar) from LTE cellular network,
It shows status "Safari couldn't open the page because the server stopped responding".
2. Apple Map "Fails" to "load the route" and Could not provide navigation (Device shows Map with "Loading Icon")
Its status shows the device is with signal (level at 2 bar) from LTE cellular network,
It shows status “A” route can’t be shown because of a problem connecting to the server”.
Action-1: I tried to perform "Airplane mode" ON then OFF, which is to "warm boot" the cellular chip/system.
Result 1-1 : "Airplane mode" ON then OFF, did not clear the problem.
Result 1-2: The device's status shows the device is worst with signal (level at 0 bar) from LTE cellular network.
Result 1-3: The device later shows a dialog box "Could not activate cellular data network"
Result 1-4: The device is useless in this condition - it could not get Cellular system working"
Action-2: I tried to perform power-cycle (slide to power off after pressing two buttons)
Result 2-1: "cool boot" whole iPhone 14 Pro Max; and then Re-Start the device see "Apple logo"
Result 2-2: This FIX the problem and Restore Cellular connection and I can use the device as expected.
Later, My iPhone 14 Pro Max would ran into the Cellular connection and the problem repeated when using the device (without WI-FI service.)
A: I noticed this problem with iOS (16.2) and files an problem report on Apple site on Jan 2, 2023;
B: The same problem repeatedly happens even after many upgrade to latest iOS (even with 16.4.1).
C: I brought my device to Apple Store for check up, and I was told there is no HW or RF issue,
D: Store's engineer recommended to do "Erase-Install" the latest IOS 16.4.1 and with iCloud restore.
E. The same problem repeatedly happens even after this Apple Store visit with case number.
Note: I have another iPhone 11 Pro Max, and it does not have this problem.
Currently, Getting Apple Support to help on this ....