I can just tell from personal experiences. I had O2 but had no connection at places from some relatives (Harz area, Münsterland). My cousin has still O2 and when we visit those places, he is dependent on wifi. Recently we were on a trip to Ostsee and stayed somewhere in Mecklenburg-Vorpommern. Same issue. I switched to Telecom as prepaid. No issues so far in those areas. Vodafone was also ok.