If I plop down a lurking monster, I do so because I want to showcase it's awesome ambush routine or whatever. Not to see it being instagibbed before it can act.
So.
Assume at least one party member rolls high. Doesn't have to be the perceptive Wisdom character, and so let's not assume DC 27 for the Stealth attempt.
But let's say DC 20.
Now, I need my lurkers to actually be lurky. That means they should succeed more often than not; let's say at least a 60% success rate.
Which brings us right back to the +12 from earlier.
Back then I kind of made it up. Now I realize I was more right than I thought.
Tldr a lurking monster that's supposed to lurk a 1st level party should have closer to +12 Stealth than a pathetic +3.
So I decided to do a little testing on this. It depends somewhat on how you handle the opposed checks. I'm assuming that out of a party of 4, two of them can be actively searching, while the other two just get their passive perceptions. That at least guarantees a minimum result from the passives, but the difficult stuff is up to the actives to find.
(I wrote a quick program to check things; if anyone wants the code, let me know.)
For a 1st level group, I dropped in a +3 and a +5 perception as the active checks. Nothing particularly special. The +5 could be from a cleric, or a rogue with a low Wis, but Perception Expertise. (Though I rather like changing that to Advantage, that adds extra complication that I don't want to deal with for this little test.)
Anyway, for the two active searchers to succeed 40% of the time against a lurking critter (ie: the lurker has a 60% chance of succeeding in its ambush), the critter needs a total bonus of +10 (average if rolling) to +11 (Take 10 straddles the +10 and +11 range). For one, two, or three players with +5 Perception, the target to aim for would be +8, +11, or +13 to allow the critter to succeed 60% of the time.
With two higher-level players in the +9 to +10 range (high Wis or Expertise), the critter needs a total bonus of +13 against just one player to succeed 60% of the time. With two players, you want a +15 to +16. With three players, you want a +17. With four players, you want a +18.
It looks vaguely like +6 over the highest party skill give you a 60% success rate, when you have to contend with a couple players rolling instead of just one. Each additional player after that increases the total by +1 or +2.
In any case, that's way too high for raw skill alone. However the creature doesn't need only raw skill. Circumstantial bonuses undoubtedly apply. If this creature regularly tries to use ambush tactics, and is in its home territory, it almost certainly has the advantage. You can slap a +5 on the Take 10 target DC and only need a +6 in actual skill. At level 1 proficiency, that would imply an 18 Dex, which seems entirely reasonable. (Alternatively, give the players disadvantage, although that may give away more information than you want to reveal.)
If we want a more generalized setup, I'll look at the 50% success rate instead of 40%/60%. For 50% vs two players, you want about +5 over their skill level. Each 5% adjustment is a +/- 1, as expected, and each additional player participating in the contest would suggest a +2 to the difficulty to keep it stable (or +1 after you get past 3-4).
In general, it doesn't feel like creatures need huge boosts to their skills (although they definitely should have more standard proficiencies). Rather, circumstance bonuses need to come into play more. A lurker hidden in a ceiling crevasse should get a solid bonus to stealth, instead of relying solely on skill.
I notice this a lot in some of the games I play, particularly those based on modules. There is very little consideration given to the environment, and how that might affect a creature's performance. Empty rooms are annoying, because there's nothing to use to make combat more interesting, and noone even considers the advantages some creatures might have, given the chance to set things up the way they'd want.