A search state is an interesting idea. I didn't think of that because something like that is not necessary for my projects (this AI demo is already verging on too smart for the sort of game I'm making, and I wouldn't want the enemies even harder for the player to evade) but something like you suggest would be great for a stealth game.
For the demo, at least, you could make it configurable. For the game, you can do the same: Let the player select some options/states to make it easier/harder. I considered the idea because I found it was much too easy to evade the AI by running around more than one corner as quickly as I could. But if the AI tried to check a little further, it would have had a 50% chance of finding me again for two corners, 33 1/3 % for three corners, etc.
Edit to add: A fuller AI could even be made harder by using learning and predictive algorithms. So for a harder stealth type game, it can learn things like the player is more likely to try using a corner that is closer and gives them more space/corners to try hiding again.