Since some weeks my iPhone 4 started to act strange in terms of showing a popup message whenever it lost the cellular network:
First I thought th is behaviour might be intended and was probably introduced with the latest iOS update. Asking my friends about it, it turned out that this is definitifly NOT normal.
So I checked my cellular provider settings and found out, that I had specified my preferred provider from the list:
I changed these settings to “Automatic” [detection of best available cellular provider] and tadaa: no more messages about the lost cellular network!