The way it's written, we can imply from the context that we stayed there recently. The second clause of the sentence contains two common triggers for the Present Perfect tense. First, the action (or in this case the lack of it) has continued until the present time. Also, the action is affecting the present time. It explains why the town is the way that it is. The tense of the first clause doesn't affect whether you can use the Present Perfect tense in the second clause. You could put the first clause in other tenses and still use the Present Prefect in the second clause: We were recently staying in a village where time has stood still. Right now, we're staying in a village where time has stood still. We'll soon be staying in a village where time has stood still. We like to stay in that village because time has stood still there. We like to stay in villages where time has stood still. Your last sentence changes the meaning to one that has a less well-defined time frame. I would suggest using the Past Perfect: We once stayed in a village where time had stood still for centuries.

...Has stood still, sounds like we are there right now. ...Where time stood still, sounds like I am explaining something that happened in the past.