I just didn't understand how their rep for doing something in town X could benefit them once they travelled 20 hexes to town Y, especially if they made a beeline for it.
It's harder to justify from a "simulationist" rather than a "narrativist" standpoint. The narrativist in me says, it's just a mechanic that enriches the story. But the simulationist in me wants the story to be consistent.
I could hand wave a couple things about reputation:
1) in this fantasy world, it's perfectly feasible that some people have mystical dreams about great deeds that occur elsewhere in the world. They have these "green dreams" then tell everyone about it, then a week later into the village gates walks the group that everyone just heard a tale about.
2) when a PC is recognized, it need not be for the deed they just recently did. Say they burned the rust temple and rep went from 2 to 3. Next village over, they are more likely to be recognized, but perhaps it will be for something they did a while back.
3) something else to explain the immediately increased chance of being recognized next town over? Glow. Confidence. Spirit. There is just something noticeable about you when you walk into town after having just burned an evil temple to the ground. Feels good man. People will sense it and start to whisper.
4) communication doves do exist in this world (see Dovecote feature in Strongholds).