sometimes it can be very tricky to find the location. There are a few clues though:
How many crowns is the contract worth? The more crowns the further away the location is.
In the text there may be more hints. The quest giver often says “in the hills” or “plains” or something. And he will add: “a long way” or something similar.
If he says a long way it may be more than 1,5 screens away.
The best guess is always to check the direction and walk as straight as possible.
Nevertheless sometimes its really difficult to find them. I tend to break off the contract if I take too long wandering around.