Riding with the Wayback Machine, in 1977 we flew into the Allagash (Chesuncook???), and they shuttled my car to the takeout at Allagash for $150 for the two of us and my 14' aluminum canoe . I'll take a dozen, thank you.
Red lake to Donald Lake cost me 435 canadian for our WCPP trip. The flight was part of trip that had waited a long time so I wasn't going to question the cost.
I planned but forgot to mention that rates are higher in areas where fuel has to be transported a great distance. This definitely applies for "North of 60" routes.
In contrast to Wayback, this summer's flights to/from the Horton, in a Pilatus Porter, came to $20,000 CDN!!!! It worked out to $4K US per person (4 of us) which is a lot, but seeing a $20,000 flight bill catches your attention. That's about $20 CDN per mile.
Float-Plane Charter Service Flights up to 40 miles Lakes including Bigshell, Glenn, Hansen, Kilburn, Knox, Linge, Larus, Mexican Hat, Murdock, Olive and others. 1-2 Passengers One Canoe -$430.00 US per drop off or pick-up 4 Passengers Two Canoes -$580.00 US per drop off or pick-up 6 Passengers...
www.goldseekers.net
So yes, if you did a fly in and paddled back to Red Lake, or to a road access point, you could still have a reasonably economical vacation including a fly-in.
I have never been in a plane before a canoe trip. But we flew in lots of Cessnas and Pipers with floats, helicopters, Beavers, Otters and Twin Otters doing environmental consulting work all over the western US and Alaska.
For a canoe trip an Otter or Twin Otter are your best bet if you can afford it.