Wan man deine Route direkt flöge, dann käme man mehr oder weniger quer über das Berner Oberland, das Wallis und die französischen Hochalpen. Da ist eigentlich recht klar, dass da kein Airway unter FL160 sein kann. Man sollte sich da auch wenn man IFR fliegt die VFR-Karte mal grob vorher anschauen. Dann wird völlig klar, dass man im unteren Luftraum zwischen Stuttgart und der westlichen Cote d'Azur einen spürbarn Umweg im Flugpan haben wird. Westlich eben via Genf, Grenoble, Rhonetal, oder eben (aber in mindestens FL140) östlich über den Airway via Zürich, Gotthard, Locarno. FRA gibt es in Schweiz, Italien, Frankreich bisher im unteren Luftraum nicht. Dies (Alpen) sind jene Fälle, wo man - obwohl es oldschool ist - während der Flugvorbereitung schon noch mal die Enroute Chart mit den Airways anschauen sollte. Da gewinnt man einen guten Eindruck der Optionen, der Luftraumstruktur und darüber, wie die einzelnen Ländern so "ticken".
Grundsätzlich muss man einfach sehen, dass es in vielen Ländern oft nicht so schön gerade aus geht wie zumeist in Deutschland. Der Grund: kaum ein Land hat
-so viele Airways
-so (vergleichsweise) wenige Beschränkungen auf diesen Airways
-so viel tiefreichenden kontrolllierten Luftraum
-so liberale DCT-Regelungen
wie Deutschland. Dazu kommen in den Westalpen ein paar sehr hohe Berge und auch reichlich Naturschutzgebiete.
Mit dem "Verhandeln" ist es so eine Sache. In deinem Fall führte dein Flugplan ursprünglich überhaupt nicht durch die Schweiz. Die Schweizer hatten daher keinerlei Kenntnis deines Flugs. Das war hier wohl der Grund warum das Erlangen einer Freigabe durch den Schweizer Luftraum so lange gedauert hat. Manchmal geht das gar nicht, denn (die annehmende) ATC mag das oft gar nicht, so kurzfristig und ohne jegliche Daten in deren System mit einem Flieger konfrontiert zu werden, der auf einmal quer durch das Land möchte...
Manchmal kann man manuell die von autorouter vorgeschlagene Route noch etwas nacharbeiten (mittels fly-over points), so dass der Flugplan, wenn auch mit etwas Zickzack, zumindest mal durch jene Länder führt, welche man zu durchfliegen sich wünscht. Das vereinfacht das Leben mit ATC meist erheblich. Problem hier: wenn man durch die Schwiz filt, erhöht man seine Chancen auf einen Slot erheblich.
Wenn das Wetter gut ist, dann fliege ich diese Legs von der südwestdeutschen Kante Richtung Cote d'Azur eigentlich nur noch VFR. Direkt am Mont-Blanc vorbei. Z.B. kürzlich St. Dié - Cannes. Ist nicht nur deutlich kürzer, sondern auch viel schöner.