Care to provide an example, for those of us who aren't 4e-knowledgable?
A good example of PC level scaling with situation level. High level play can mean that the PCs push the world around, but the world can also push back. Super hero PCs might seem pretty impressive in the "normal" world, but if they travel to, say, an elemental-ice-demiplane in which they must resist glaciers that move like falling sleet, well, they don't seem so super anymore.
Some games, like those with complex NPC character sheets, are going to be more time-consuming at higher levels as those sheets become less wieldy. But if "high level" just means "more chaos," then I suspect all games will suffer the problems brought up by innerdude. A GM can design a dungeon or situation with an obvious problem and a best solution, but "high level" can mean that PCs can create their own best solutions, or oftentimes PCs can use those levels to create more obvious problems.