Alphastream
Hero
I've never had an issue with this. I see 4E as working to capture the story of the PCs, and that story is one of increasing challenge (which ends up being a challenge appropriate to them, since they also increased in capability). At low levels they are involved in things that are low in challenge; the guards they find are guards that are not particularly capable. As the party reaches higher levels, they are interacting with guards that are much more capable.I would suggest that 22 Perception is the issue. Why are these guards so amazingly perceptive?
While there are a few issues (say, in Epic you come back to the same tavern you visited in Heroic), overall it really works. If you come back to the heroic tavern, the DM shouldn't really be requiring checks. Anyone that requires a check is an epic threat/NPC that has come there due to their reputation, rather than being the same small-time crook from level 1.
For some people this system is really bad. It hurts them to see the DCs of locks increase as their PCs level up. I have always preferred this. The DM can easily explain why, and it really is a waste of time for an Epic PC to have to in any way hear about or deal with a heroic tier lock.