"A problem I see with reoccurring characters and/or villains that are given an early introduction is that some characters will try to fight them immediately. I understand that the DM will usually try to show that they are really powerful and that the PCs can't win, but some characters will try to do that anyway....whether it be a stupid barbarian that always picks a fight to a noble paladin that's willing to die in battle to try and protect people."
This is such a strange thing to ponder about, or to note as a problem that is happening to multiple people that I had to write something here about it. I mean, it's so opposite to the way that real life works (not to mention the way that most games run) that it's like I stepped into a bizarro world.
I mean, honestly, the fact that players might expect to survive (and win) any given fight isn't entirely unreasonable. It's a symptom of players being used to easy victories from video games and from games that are designed around expecting frequent, relatively safe combat that the players are all but guaranteed to win (3rd/4th edition D&Ds and Pathfinder, respectively.) When you've played a hundred hours of a game where cutting down your foes is the preferred method of combat resolution and when that's worked for you every single time because the game you're playing has detailed rules for that and for little else, that becomes the baseline. Oh look, it's the bad guy, being evil in front of us. Let's go ahead and kill him, obviously the DM wouldn't put him there if we weren't expected to win...
And, as a DM, you should know that's the expectations of your players. I personally make it a point to tell people that haven't played with me before what my personal style is like. It's only good sense- you don't know what your players are going to expect going into the game the first time you play, and it's good to make sure that your expectations are all on the same page. Which means that, since it's a two-way street, you should have a pretty good understanding of what your players are like, their tendencies, their expectations of you, and what their play is likely going to revolve around.
And after doing all of that, how on earth are you still going to have a problem with this sort of thing? I mean, honestly, what baffles me is that, knowing that their players are apparently aggressive and careless, and knowing that they are likely to go towards "heroism" rather than "common sense", DMs have nothing in place, setting-wise, to prevent said homicidal wandering murderhobos from doing things like killing the Arch-Duke of Maleck-Kreb. You know, like guards? Or some sort of reasonable protection like real-life important people use? If the players are able to immediately slay the villain the first time they see him, how did he make it far enough along to be a threat in the first place? Why wasn't he assassinated in his daily rounds of Malicious Peasant Mockery last week? How does somebody with such feeble defenses become a villain? Why does he make it a habit of appearing sans body guards, defensive enchantments, or self-defenses in front of fully armed and armored strangers?
If there are body-guards, soldiers, guardsmen, mercenaries, or what-have-you, and the players charge to their deaths, then what's the problem? Obviously they're going to die, and that's good, because the players now understand that taking on the big bad guy isn't an idiot and he isn't defenseless. Taking him on will require planning, better equipment, and possibly some help. That's exactly what should be happening. So you're out one (or more) characters and now the main villain looks even more impressive and intimidating, and now you've got a lot of interesting things to talk about. Surviving party members can mourn the dead. The villain has an excuse to increase his extortion, and the suffering villagers might recognize and hate the surviving "heroes" as the source of their suffering. "You're the friend of the damned fool who's responsible for this, aren't you?" The player made a serious mistake, and now it's corrected by removing the character from the game.
So I guess I'm trying to say that I can't understand a single part to this problem. The single negative fact, that a PC has died, can easily be turned into an important learning moment, a potent roleplaying moment, and some world-building all at once. It's literally a win-win... unless the player's a bad sport about it, of course. But that's a totally separate issue entirely...