here is the coverage map from verizon's website. Verizon has the best coverage in Maine in my opinion.
The west side on Northern Maine in White is still very undeveloped (ie few people) There aren't even town names in that area, just numbered plots of land in many cases
If you are travelling throughout Maine in populated areas, you shouldn't find too many dead spots, but rural travel in Maine is another story.
__________________
|