Malheureusement on ne peut pas faire grand chose.
Les chemins sont déjà optimisés comme il faut, mais la décision de t'envoyer à Paris ou à Frankfurt est géré par le DNS et outrepasse les décisions de routage. C'est pour cela que, quand tu rebootes ta box, tu vides le cache DNS de celle-ci et tu changes de destination, sans intervention de ma part.
Essaye de changer tes serveurs DNS dans ton PC (attention, il faut aussi changer les serveurs en IPv6) par du Cloudflare ou autre pour voir. Suivant qui (càd quel serveur) fait la requête, la réponse pourrait être différente.
Par exemple, on a un peering privé avec Google à Frankfurt. Quand tu interroges "google.fr", la grosse majorité des réponses DNS te renvoient vers un serveur allemand (d'où le "fra" en début de reverse), donc ping optimisé etc. Mais si le DNS te renvoie un serveur français ("par" pour paris), bah tu feras tout un détour (dans le réseau de Google) sans que je ne puisse rien y faire.
Donc essaye de jouer un peu avec les DNS, ça pourrait donner de meilleurs résultats.
Edit: si tu connais des IP des serveurs français et allemands, je peux forcer le routage. On peut tenter ça aussi.