I would be remiss if I didn't mention one "other type of Caching" you might want to consider if you're iinto wilderness and numbers. Just north of Old Town, which is just north of Bangor is the small town of Costigan. There is a very well maintained paper company road(the Stud Mill Road) open to the public that runs easterly from Route 2 towards Eastport, Machias and some of the other beautiful coastal towns suggested in this thread. My wife and I went there yesterday, started caching around 10:15 and stopped fairly close to Machias at 5:15. We saw moose, deer, rabbits, turtles, eagles, hawks, turkey buzzards, you name it. We also logged 90 caches. While this is not the type of caching that everybody likes, check the cache density and the route and if you like the looks of it, then have at it! There are a lot of very good suggested caches mentioned by others along the coast all that you will likely enjoy.
Sometimes the road less traveled is less traveled for a reason.