Just make the system slightly more complex.
Divide the goods to a few categories. Give each category an actual demand curve, something like price = x - quantity*y (or possibly something fancier). Price is the price they are willing to pay per unit of a good, and quantity is some aggregate long term average number. x (base price) and/or y (price elasticity) might vary per fief types too. Y probably has to vary with population count or prosperity or something in fiefs too. The price should probably not update dynamically, but at some interval (24h maybe?). What this would do is make people have to really vary trade routes since if a trade route becomes too popular it's profits will plummet (too much supply). What this also does is make clans really hate people who dump goods in their villages...
...except I think it'd be a good idea to remove the ability for fief owners to set good prices. Especially when the above removes the selling price aspect of the good price setting. Have default good price be some arbitrary number z (like 15 it currently is) and have some supply function which is basically based on a) prosperity b) quantity of each goods category brought in. You could give supply an actual supply function too if you wanted, making prices higher if more goods are asked with the same amount of stuff traded in.
It might also be a good idea to make prosperity increase on each good sale AND purchase by a fraction of the prices, but any taxation should reduce this fraction. This would be real life equivalent of well, capitalists getting profits on their trading. I would assume that the selling and buying prices contain some sort of a profit marigin. Or well, this really depends. Currently the tax is paid by the player regardless of if he is selling or buying. I'm all for making the taxation hurt seller only, which would translate to lower prosperity gains with high tax when selling goods to players.
My hope and prediction is that these changes would make the system complex enough that with the right values for the variables if free trade still isn't viable, at the very least some sort of trade deals with people would be totally worth it to maximize your profits. Even more awesome would be if each good had it's own demand functions so basically if you buy onions from Balanli they are probably going to be worth a shitton in Shulus unless other players have already figured that - that'd be a thing that would pretty much require you to remove distance bonuses though.
It sounds like a fairly complex system, but honestly it isn't that complex. The complex part is to set all the parameter values correctly (and making the demand and supply functions such that price will always be above 0 and never above some parameter)
