Sorry for delay. I like your option the most from proposed. Certainly. But I think it is - in general - good idea to provide some consequences of staying in one place and repeating the same things all the time for players. So I would extend your option with this addition(as I like the idea of "step dice" very much):
- with each attempt of searching, after the first one - player also roll d20 -> rolling 1 on this, makes something bad happen to him/her. The next attempt would with d12 and also 1 mean bad luck. Next d10 and so on until d4.
Or alternative without step dice (probably even more handy and elegant) :
- with each rise of DC by 1, Critical Failure threshold rises also. So with the first roll searching, DC is normal and only rolling 1 is bad lack. Second roll its: DC+1 and on 1-2 on D20 you get Critical Failure, third it is DC+2 and 1-3 threshold for CF, and so on...
So it's like a mix of 1st option and 2nd, but with nice progression of risk and push your luck aspect:) And the PC should not be afraid to roll - the first time:) (as many would be with clean 2nd option)