Found the problem!

As far as network infrastructure goes, Germany really is a developing country (sometimes I feel in the wrong direction).
There are regions right outside of Berlin, where there is no cellphone coverage at all.

We have three network providers and a whole lot of resellers who usually only use one network. If you happen to be in a region where your provider/reseller has no coverage then you're out of luck.