We evaluate a potential scenario for future Air Traffic Management (ATM) system in Europe and benefits it could bring to the Airspace Users, where a network manager (NM) has a mandate to manage capacity in the network and define capacity requirements to accommodate anticipated demand in a safe, efficient and environmentally friendly manner. In the considered scenario, the European airspace is still highly fragmented, i.e. capacity is provided by individual Air Navigation Service Providers (ANSPs) on a local/country level, but the assumption is that cross-border capacity provision is possible and is optimized in the capacity planning process led by the NM. Capacity planning usually starts a long time ahead of the day of operation to ensure that sufficient resources, including Air Traffic Control Officers (ATCOs) are available to safely manage traffic. At the time of making capacity decision, i.e. allocation of ATCO resources for a day of operation, one of the main challenges is considerable uncertainty regarding the demand: overall traffic volume and demand spatio-temporal distribution. The fundamental trade-off is between reducing the capacity provision cost (within-border and cross-border provision) at the expense of increasing expected displacement cost arising from re-routing or delays. To tackle this, we extend a decomposition approach that we proposed in [1] to allow capacity planning for cross-border provision. Furthermore, we present a numerical study based on real capacity and demand (traffic) data to study the effect of allowing cross-border capacity provision. The results suggest that there may be significant potential for cost reduction in cross-border control, especially for risk-averse decision makers.