So I just started DMing for my first actual campaign last week. The first session went pretty good, a few hiccups here and there, was nervous as hell but it worked out. So safe to say I'm pretty new to this whole thing. And the #1 thing I'm having the biggest struggle with is balancing out the enemies. Not just with the random encounters, but the bosses. Currently, the main threat of my campaign is someone that is essentially all powerful. He got that way when a crazy scientist created a toxin that, when consumed, brought their greatest fears to life. Being as the scientist was extremely narcissistic, his greatest fear was an all powerful version of himself. Thus, he was created. He isn't completely impossible to beat. The main plot is having the party discover the one way to bring him down, which involves them resurrecting the person who created him and having him show them how to defeat his own creation. But during their travels, I was intending to have the villain occasionally show up to the party and mess with them. The villain has a sick love of letting people grow in strength and building up their hope in beating him, just to rip that hope away. Their first encounter with him, I was intending to have it where (if the party attacked him) he would act as if he was actually getting hurt, just to pop up behind them and break their spirits by letting them know they didn't actually do anything to him. He never has any intention to actually kill them, cause that'd ruin his fun. My thought process was that, seeing this would anger the players and want them to do anything their power to figure out how to beat him. It would push them forward. But I've since been watching videos of it, and now I'm starting to think differently...If it would actually demotivate my players to keep trying if I made a mary sue villain that could only be defeated by one (maybe two) method. So now I'm thinking against making him immortal, but figure out what to actually make his power is difficult. And it also makes me wonder if there's actually a good way to make an invincible villain. A way that doesn't dishearten your players.

Give him an ability like guardian nagas and liches have, where he can be defeated temporarily just fine - although it should be very difficult, he should be destructible - but can't stay dead without extreme measures that may not even exist.  Spoiler for Rime of the Frostmaiden:

In fact, you could have him be easy to defeat, but every time you do, he comes back stronger, so the pro move is ignoring him until you have a permanent solution.

Ravenloft's Strahd will absolutely make the players really, really hate him and has an ability that makes it difficult to kill him outright. If that's what you're after, give the Curse of Strahd campaign a look.

As quindraco indicated, invincible-but-not-quite in D&D often comes down to the entity, upon destruction, being moved away to a theoretically safe place to regenerate. A lich' phylactery is the obvious example, but any variation on that theme works. The convenient thing about this is that while this pretty much leaves just one solution for permanent eradication, just how difficult it is to achieve that (and finding out how) is relatively easy to manage for the DM - a phylactery is typically very hard to reach, but maybe the lich had to/wanted to move it for some reason that has nothing to do with the PCs or maybe them finding out about it is sufficient for the lich to act and thereby make it temporarily easier to get to.

Another variant on this is to have the invincible entity's survival not be tied to a location or item to chase, but to a singular weapon, spell or ritual that is the only thing able to truly destroy it - like silver weapons for lycanthropes, but much more extreme - with said weapon/spell/ritual needing to be found/restored/researched/components collected for. Regular weapons and spells might drive it off and/or weaken it for a while, but without the specific required tool it keeps regenerating/getting resurrected.  

The issue isn't the villain's apparent "Invincibility" so much as it is the connected sense of futility. The players need hope in order to be heroes.

(1) The players should believe that the villain can be defeated. Maybe there is a prophecy that says that something like this has happened in the past, and they need to track down a scroll/survivor/etc to learn more.

(2) Each encounter should provide a sense incremental progress. Maybe the party is carrying an artifact that slowly attunes to the villain over time. The longer the party can keep the villain busy, the closer the artifact comes to being fully attuned.

(3) If the party can't directly harm the villain, maybe they can thwart him in other ways. Negate his attacks, block teleportation, kill minions, etc... If the BBEG begins to show frustration, then the party knows that their actions are consequential.

I think I would instead have someone else discover that the villain is invincible and assign the party to find a way to defeat him.

As an aside, I don't particularly like the origin story of the villain.  Where does the power that the all-powerful villain has come from?  If it came from the victim of the toxin, that would imply that the victim had the potential to become all-powerful.  If it came from the toxin, there exist materials in the world with enough energy to elevate anyone to becoming all-powerful.  Either way, I have trouble envisioning a world where either of those exist while also containing the gods and other beings of power that are necessary for the typical variety of D&D classes.

I have custom gods that I created for my campaign. And yes, the toxin has the ability to create something that is powerful enough to rival even the gods themselves. The toxin isn't the source of the power itself, it can manipulate and absorb manifested power from the elements to clump together to an infinite limit. The only limits to its capabilities is garnered by the fear a person has, because that's where the toxin gets its power. It infests the creatures brain and reads it's every thoughts, analyzes what falls under it's fear factor as it's the most vulnerable part of a person, and manifests something similar to it. The gods would rid the world of the toxin, but the current villain can even control them, and he's been doing so for the last 10,000 years. The story centers around a land that is boxed in by a massive wall which the villain commanded the gods to create long ago, outside of the walls is where the toxin resides. Now a days almost no one knows what's actually outside the walls. Why does the villain do this tho? Because he gets off on seeing people hope. He loves leading people on, thinking they have a chance to beat him, just to rip it away. Killing everyone isn't fun for him, he loves to play with his food so to speak. But being alive for 10,000 years, you tend to get bored of being all powerful and actually want a challenge. Then one of the gods, a god of the future, tells him of a group of adventurers that will soon overtake him. He could of learned how they would beat him, but his narcissism made him so desperately want to prove fate wrong, so he only learned as far as who the adventurers were. Then he disguised himself as a ruler of one of the lands, manipulated the people of the city to believe that he was actually their ruler, and spent years locating all of the people mentioned to him. He even created extremely powerful items that he wanted the adventurers to find, to make them believe even more that they'd have a chance to beat him. He's just an evil troll basically. That's the basic gist of it, I'm still working on fleshing out the details. But I liked what the first person said, of having him be easy to beat initially but he can come back. It would fit since his spirit can literally control death. His body is just a vessel that he uses. Being as he is a creation of the toxin, his body is just a clump of manifested magic.

I don't know.  A "toxin" that can create a being so powerful that he enslaves all the gods at the same time and rules the world with absolute power for 10,000 years (which is about 1.5 times longer than human civilization has existed in the real world) sounds more "ridiculous cheese" rather than "awesome foe for a campaign."  I think you could maintain him as a credible threat (and actually make him feel more like a real threat) if you toned the power down considerably.

I've been trying to figure out how to tone down his power that would still not change the story as a whole. Since it's my first campaign I don't think I understand the balance system enough to be able to come up with a decently strong villain that would still keep the story the same as a whole. That, or give more reason to his power. Cause like, one of the gods is a god of chaos, so he could side with him...he could be the reason why he's able to control the other gods. I don't know, I'm still trying to work around it. But I definitely don't want him to be as strong as I initially made him.

Sounds like you need a good ol' fashioned "Wizard of Oz".

Maybe your BBEG has already been defeated, and someone has been mascarading as them for a few thousand years.

The thing about a villain like this is that you've set him up as an unstoppable overwhelming power.  Really not someone that they actually have a chance against, especially if they know the lore that he likes letting people get false hope about being able to beat him before he crushes them.  Rightly or wrongly, players hear stuff like that and tend to react by assuming that either there's no way to win or that victory is going to be something that relies on DM Ex Machina.  I get that you want him this powerful for your game's plot, but the plot itself might be overdoing it.

Does the power come from the toxin or from the fear, make up your mind.  If it comes from the toxin, why did the gods not know about the potential power of it before the incident?  If it comes from the fear, that implies that the person with the fear has the potential to be greater than the gods, why didn't the gods know about him?

In the past, I have had my players face lieutenants of the BBEG, who were hard to beat but which were defeatable, and then for the actual BBEG themselves, I made them genuinely indestructible.  The point was not to kill them but to have the players weaken them throughout the campaign. Sufficiently enough to banish them from the PME.  You have to be careful, though, that your players will not be feel cheated or get frustrated with the ending.   It should be hard enough to feel like a real victory, but not so hard that they get worn out, tired and bored of it.  

The power doesn't come from the fear, the fear is the basis for what the power of the toxin creates. The gods weren't aware of it because the gods in my campaign aren't as insanely powerful as they are in most d&d campaigns. The gods that are that powerful aren't known in this campaign, they exist outside these walls in a different part of the world and don't bother with this land. These gods tend to not bother with those that aren't their followers. Only one of the gods is actually able to know the future among the 12 that reside in this land. There will be a reason for why he didn't inform the other gods, but I haven't come up with that yet. But yes, the toxin does have the potential to create beings that are even more powerful than the gods. I'm debating on having it be the gods outside of the walls that gave the toxin the power in the first place. Like, they plotted to destroy the 12 gods of my lands because they were a mockery of the other gods due to their weaker power. I don't want it to be solely the BBEG that was able to create the toxin singlehandedly, I've just been trying to figure out where else to make the power come from.

If I was going for a villain wanting to taunt the party, I'd make a wizard.

Invulnerability and Project Image are good ways to have the villain there to taunt the players. Use Scrying and other means to keep tabs on them. When they know the players are about to go face a day of battles, gather a few spellcasting minions for some Dream spells to deny some long rests. 

A base protected with permanent Guards and Wards, some Glyphs of Warding traps and such can make for a nice dungeon crawl to weaken the players before getting to face the big bad wizard and his planar-bound monster.

They might defeat the wizard but unbeknownst to them he had secured a Clone in a secure Demiplane. They might go on many adventures until the wizard has secured enough resources to get revenge - and now that he knows the party more directly, he's even more deadlier than before. Perhaps they befriend an NPC who has been with them for a while but one night the wizard summons that NPC into a demiplane via Gate spell and with a combination of Imprisonment and Magic Jar spells he takes over that NPC with his own body secured in the gem used for magic jar, now around this NPC's neck. In the body of the NPC he tries to sabotage the players. Discretely taking moments to send messages to his allies to thwart their efforts and guide them - perhaps even using them to collect items that could be combined to powerful effect. And if they discover him? Well now what do they do? Kill their friend? And if they do - His soul goes into the gem, into his own body and out he comes, freed and able to teleport away (Metamagic Adept feat - Subtle Spell + Teleport). Perhaps he even takes their NPC friend's body with him to raise it as a zombie just to rub salt into the wound when they next face him. 

And the best part, aside from unlimited gold and time before meeting this wizard, this is perfectly RAW for what a player could do. All done using spells and features they could have themselves. 

As a DM you are not bound to the rules and can do what you want. But making a villain so effective using the same rules players use, that makes it so much sweeter.

I love wizards.