The problem isn't that attacking someone as becoming harder and more time consuming... location-based battles was necessary for this game to evolve. The problem is that "dueling" someone is no longer worth the effort. Duels are arguably the primary selling point for this game and the vast majority of players either do or have taken part in them... and at this point it is simply not worth it to spend the time and energy to chase someone down hoping to beat them for: some pocket change that they could make back in an hour of working a money job, and a loss of health that they will regenerate in a few hours at a hotel.
Two answers, in my mind:
1) Separate "fights" from "duels". Duels happen in towns and should be initiated at a saloon. Fights are location-based and constitute everything from a robbery to an assassination.
2) Make "fights" more important, with more lasting and substantive effects. A low percentage chance that a loser will drop a random inventory item (perhaps not random, but rather value-based depending on the disparity of damage done). Possible injuries sustained during combat that have stat or ability penalties, disabled limbs and such that heal independently of overall health points. While you might have a smaller percentage chance of an injury when losing a fight, or it's a minor effect, you are almost guaranteed of a major injury when you get KO'd. Then make KO's dramatically shorter so that the victim is injured and vulnerable, instead of getting a 2-day free pass to work jobs. This would help town vs. town fighting become more relevant.
I also think the next evolution is some sort of posse battle system, similar to fort battles but with far fewer losses and no transfer of ownership. This would give duelers and soldiers a way to fight their enemies without having to chase them across the countryside, especially when that involves leaving their town undefended.