I can see serious problems with AI looking around as soon as the player has sneaked. First, how far do they look? What is the range? It can happen that stealthed player just stay out of this range and use a bow, essentially needing to work even less than now to pop enemies.
Yes, it's very involved to write a good algorithm to find a stealthed player. Especially one that players wouldn't soon find ways to exploit with impunity.
I think it's probably better to just nerf stealth to having a debuff (call it "spotted"), where once you exit stealth you can't re-enter again for 2 turns. Perhaps also give the AI an expensive method to force players out of stealth it knows are present (call it "flare" for mages, "track scent" for animals) for 8 AP.
Often limiting abilities are necessary to bring them down to a level that the AI can deal with. If they feel up to writing some sort of next-gen AI, more power to them. But if not, this is how you fix it.
