In my group we always employ the 'Shenanigans' rule.
I have a couple of 'creative' players and though they may swear they are not cheating, they may be doing it inadvertently or from sheer ignorance (or they may be untruthful). Thus the birth of the 'Shenanigans' house rule set.
We add one rule to cover all cheating that is detrimental enough that if caught, the player would be at a severe disadvantage but not out of the game. For example: our shenanigan rule for cheating in Catan is as follows:
You start by discarding your entire hand, If you have no cards in hand you must remove a city, or a settlement, or a road and finally a development card. If you have none of these things to remove then you are simply removed from the game. Zero tolerance. If you are caught cheating three times you are removed from the game.
The way you call 'Shenanigans' is a lot like the classic card game of 'I Doubt it'. After a player takes an action, anyone can call 'Shenanigans'. If the accusation is accurate then the player who was accused is given the penalty as described above, if it is in-accurate, each player has three strikes; the first three times a player wrongly calls 'Shenanigans', there is no penalty. If they are wrong a fourth time however it is considered harassment and they are instead given the penalty.
This has proven to be equitable for all involved in our group because we agree to it at the outset.
In your case above, I would have called 'Shenanigans' when the player tried to build the road and they would have had to discard their entire hand.
If you have more creative players, you simply need to get more creative with your penalties. The important part here is that everyone understands at the outset how it works and that you make sure everyone can still have fun playing this way. Otherwise you may find yourself lacking a group of individuals to play with.