2. what would be the best way to make these monsters look for you?
3. would you play this game again after you beat it?
If you want a 'perfect' searcher, have the NPC that's doing the searching walk back and forth, slowly working it's way from one edge of the map to the other. Obviously, there are methods to escape this type of searching, but it's much better than randomly wandering around. Maybe give the character the ability to make duplicates of himself, so that he can distract the searchers.
Of course I would play it again! Add a high score function, based on time survived (and maybe some other stuff), and it will become much more replayable.