That's a plausible way of solving the trade issue, and it's not unlikely they'd be willing to do something in exchange.
The Twin Towers? Two towers enchanted with a casting of Rite of Way that requires both ends to work together to cast it.
That way both Middenland and Eonir know that the other can't use it as a back door into their territory.
We also know, I think, that Tower scale enchantments can be of larger scale and are much easier to combine enchantments of multiple Winds or runecraft because there's enough space to physically segregate them. Having anchors on both ends might also be safer/more reliable.
We might also be able to include enchantments so that merchants without the right permissions can't remember the details.
Another viable option would be for the Eonir to control both ends, and for the Eonir to control the transport. That would avoid having human merchants within Laurelorn, which would be much more secure for them. It's less secure for Middenland, but has the advantage for them of putting an Eonir garrison on the Great North Road, reducing the cost of securing it.
This may be particularly attractive if two towers, one on each end is insufficient. If multiple towers are required for the enchantment; then it's likely to need more help building and maintaining the towers which I think the Eonir would need to do,
Thinking some more about what would be required for this proposal. I suspect we'd need to codify/optimise Rite of Way so that we could share it with the Eonir, as I doubt they'd be keen on a massive piece of magical infrastructure that cast a spell they couldn't cast leading into their kingdom in case of 'undocumented features' that the Empire could later exploit.
If we were doing this for their benefit I think we could sell the Eonir, or at least magical Houses if not a Grey Lord, on collaborating with Mathilde in the codification process, or potentially sharing books on Ulgu theory to make it easier to describe in a way that they can more readily understand.
They may also be willing to collaborate on the enchantment process, sharing some of their knowledge on the subject, ensuring the enchantments themselves aren't compromised.
Generally; although expensive in AP, I think this is a really good idea to cement ties between the Eonir and the Empire. Both from the process of building the infrastructure and the results.
I also think it could relate to the Waystone project itself. This is the kind of magical infrastructure that may be much easier to build on top of a Leyline, or if each tower is built around a Waystone.