That means the character has nearly as many as half as many character searching for them.
And there's always the classic "Wildshape into a tiny unassuming critter" trick, which the Druid has had access to since level 2.
Even fantastic characters fail sometimes. If 5% is too high for you, play a halfling and/or take the lucky feat. How a fantastic character handles failure is AT LEAST as defining as how fantastically they succeed, IMO.
Sure fantastic characters fail, but there it's of special note when said failure is because the DM decided to arbitrarily used a houserule that introduces the risk of auto failure even when you've pumped your stats, class, skills, and features into a thing when that failure didn't exist before. Unless the character can go back retroactively and change their race to Halfling, they don't really have a choice.
And as mentioned before, it's generally these kinds of rulings that make players not really want to make skill rolls and instead resort to magic, as the effects are usually more explicitly spelled out and DM's never ask the spellcaster to make a check in order to ensure he's pulling off that complex series of gestures and utterances in the correct manner.
If I wanted to introduce this character to failure I'd acknowledge the fact that just because the character got past a bunch of guards doesn't mean they'll actually succeed at whatever they snuck in to do. There's so many ways for things to still go wrong that don't really require a houserule of that kind.