As I was thinking about level scaling (wich I hate in general), I thought of a more subtle and realistic approach. Make the monsters a bit smarter. Only those with working brains, obviously.

1) First, you give the PC a 'danger level'. A number, influenced by class, race, level and to a lesser degree by stats and equipment. Possibly also other things, doomed status for example, or artifacts.
2) Enemies respond to the danger level, comparing it to their own 'danger level'.
3) If they see it as very low, there is a greater chance of them ignoring the PC (might vary with enemy type). If they see it as low or medium, they're more likely to be aggressive. And if it's high, they'll try to avoid a fight. Some enemies will do that by sneaking, some by running, some humanoids might even surrender or try bribes.

The sneaking would be a complicated thing to implement, but it could also be used for aggressive monsters, assassins and such. And you could have the stealth skill make it much easier to spot hiding monsters. And have the Search command look for any hidden enemies within line of sight (an opposed check, I guess?).