You don't have to have encounters be trivialized to feel progression. You just need to have it feel easier, which it will. Even with enemies always scaling with your level as level does not dictate strength. Itemization and Perk selection largely does.
Trivialized means you run absolutely no risk of dying and everything dies in a hit. Things should be EASIER, but never trivial.
What's the point of a game without any sort of challenge? How would Chess be if you could move an unlimited amount of times before your opponent could? You knew you would win every game? That gets old REAL fast.
But scaling places you've been/enemies you've fought in the past to keep them relevant to your current level should trivialize at least the weakest enemies/places.
Hell it could be argued that after some arbitrary level every "normal" enemy should be a trivial encounter with maybe one or two standing out as actual challenges. I LIKE the idea that if I'm past about level 30 or so NO bandits pose a credible threat to me. By 50 only the most powerful enemies in game should have any chance of combatting me, after 50 I should eventually be powerful enough to take them easily as well.
I don;t want ridiculous enemies being thrown at me every few minutes because of my level either. Part of what ruined oblivion for me was the act that there was no such thing as trivializing an area. That very first places you went to in game? You come back to that at level 30 and the enemies will be as powerful as you. That's not fun the enemies there shouldn't just get better.
The idea of areas being "zoned" to a level range and enemy types being available only in a certain range of levels (bears to level 20, bandits go to 30, draugr go to like 35 etc) makes the leveling system feel more realistic. There should be some instances of trivialization, but there should also ALWAYS be a non-trivial challenge ahead.
Anyone else remember morrowind and getting to higher levels with great gear? Nothing in that game could realistically stop you but there were a few things no matter your level that you'd be an idiot to mess with (Gaenor anyone?). IT didn't stop the game form being fun.