Well, specifically, I was thinking of Northern Europe (Norway, Sweden, Finland)
Oh yeah, that's true, Norway is fun, I forgot about the north. In the US, every house has phone coverage (subsidized), but it's wired. Also, trains go through places people don't live.
In 2005 I was working on a messaging system for tracking trucks over cell networks through Europe. One of the requirements was to be able to survive without coverage for a few weeks at a time. Part of that was because of the complex patchwork of standards throughout Europe, though. Not sure if that has changed. One thing is for sure: a good cell-phone blocker could block them all.