I love the idea of having region/nation specific airlines. I think it would add more sense of place, and make choosing a location for the airport a lot more meaningful. Currently the climate is the only thing impacted by location, and that is very immersive.
As far as back stories go, I think they should also seperate major carriers, from their regional counterparts. For example, SkyFly could be a major carrier, operating 737s, A320s, and 777s. SkyLink on the other hand could be a regional carrier owned by SkyFly, with the same livery, and operate CRJ700s, and ERJ-140s. Basically how most US carriers (and I assume most European carriers as well) operate regional aircraft under a different company (United has United Express, Delta and Delta Connections, american and american eagle etc).
Combining these features, the major carriers could operate international flights much further than their regional subsidiaries, so using your example Maple may offer a contract to an airport in England, or Russia, but Maple Express would only offer contracts to airports in Canada and the United States.