Edit: on the topic of players who enjoy high execution characters, is there a way to reward that style of play in ways other than MAXDAMAGE combos?
UMVC3 Morrigan's entire neutral game is high execution. It's not just high execution but you also have at times adjust execution on the fly to match the other player's actions (ie. when they cross under you or teleport against you).
UMVC3 Viper has always been S+ tier in theory land but is held back by high execution requirement all around. She can lock down the ground with Seismos and Beams thanks to her jump cancels but doing Rapid Seismos is tough. She can convert Seismo hits into a full combo with great execution. She has good mobility options with high execution along with some crazy mix ups as well. She has some potent defensive options with high execution thanks to her focus attack options. Pressure as well. The funny part is that most of her BnB combos aren't even that hard... it's really the neutral and defensive/pressure options plus how to use them properly is hard with the character. Messing up an execution with her gets her punished hard because of mediocre normals (ie. you get something you don't want and you get Dive Kicked for your troubles or air thrown).
Of course playing Melee in general because of the movement execution. Same for the Marvel games as well especially nowadays with plink dashing being so common. It creates a huge gap between players when it comes to movement. Someone who is properly using plink dashing with Dr Doom looks way different than someone using standard dashing methods with him.
Execution can help you with a lot of option selects as well. Some option selects aren't as easy to do as others and many require a lot of inputs at once which requires execution of course. So characters with many complex option selects are generally going to be execution heavy as well.
And finally you can have specific high execution "just frame" moves like EWGF from Tekken which are very timing sensitive powerful moves.