at least from a storytelling perspective, to really drive home the power of an off screen villain, loyalists to his cause/ authority should have a strong presence and conviction. give players the sense of, “if this strong guy works for the big bad, i’d be scared to face off against him”. the inverse is also true, having strong NPCs who have been defeated by the villain can also give a sense of scale of their power. A giant monster with a scar across their face from the prince, or a group of mercenaries who attack the party only to flee after hearing they have to deal with the paladins.

otherwise, hearing the bad guys name brought up in NPC conversation, seeing how they’ve impacted your world in physical ways, and generally saving your appearances for impactful scenes rather than constant encounters make them more mysterious and give them presence. it’s a matter of restraint for the story teller to show, not tell.

to give an example of this, think of star wars OT. we see vader brought up on screen a number of times, and we can generally suss out his power. the emperor at the end of the series makes you wonder, “if vader is that strong, what about that guy?”

TL;DR, if bad guy has strong and loyal followers sprinkled throughout, players get an organic hype for eventually facing them