I don't know how this didn't occur to me earlier in the nine years of running and playing this game (and in fairness, it's possible it did and I just didn't remember,) but - to preamble a bit - there is a challenge one runs into as a DM running D&D:
How do I make my players scared of a monster?
To be sure, you can have a monster do insane amounts of damage. My 17th level party of Ravnican adventurers has been charged by Borborygmos to slay a treacherous Ancient Wasteland Dragon (from Kobold Press' Creature Codex) who tried to murder him and the Gruul member of the party (while the two of them were engaged in a duel challenge for the role of Guildmaster - the Loxodon Storm Sorcerer in the party wasn't doing super great in the fight so honestly this probably saved his ass). An Ancient Wasteland Dragon has a line breath attack that does force damage - 20d8 worth of it, with a dex save for half. That's an average of 90 damage, which is a good chunk even at high levels (especially when you've taken two oak trees to the face swung by a 20-foot-tall cyclops).
Still, here's the thing:
As a DM, sure, we want to challenge our players, and that challenge usually involves the threat of character death. It's a game that's largely about fighting monsters, and those monsters aren't going to seem like much of a problem if the players are guaranteed to survive (though as a side note, if I were running for younger kids, I might subtly do away with Death Saves and have characters knocked unconscious simply be stable).
Basically, how do we make a monster that will send a bolt of panic down the spines of the players, forcing them to re-think their entire approach?
Simple: We make a monster that is immune to all damage.
The thought occurred to me while watching a fan edit of a cutscene in Alan Wake II. Without giving too much away, there's a point in which a seemingly friendly character is taken over the Dark Presence - a kind of supernatural embodiment of the Jungian Shadow, and the player character, who thought they were just having a conversation with an ally, is forced to flee from their now-monstrous ally, who seems to be able to take an endless number of bullets and shotgun shells to the chest and barely slow down.
While true damage immunity is uncommon, there is some precedence in Curse of Strahd. There's a mechanic (again, I'll be vague for spoiler reasons) by which the eponymous vampire can take significantly more of a punishment from the players while he stalks the party through Castle Ravenloft, and will appear for a time to be effectively immune to any damage.
Strahd himself is fairly threatening, hitting hard with attacks, with a number of powerful spells at his disposal, but the standard 5E vampire is built in a rather unusual way: the vampire doesn't actually do a ton of damage, but they're extraordinarily hard to kill thanks to their Misty Escape (a feature that, after an argument that got more heated than I'd like to admit, my best friend explained to me even gets around the primary "radiant prevents regeneration" workaround to taking down a vampire).
In our case, though, I think we're trying to make more of an "implacable man" - a monster from which you can run, but not hide, and one who moves slowly not because it's in any way hindered, but because time's on its side - it'll catch up you eventually. And being immune to damage will give it all the time it needs.
Naturally, an overuse of full damage immunity could start to feel like the DM just cheating. We're building adventures for our players to achieve some kind of victory. The Darklords of Ravenloft are functionally unkillable because the whole point is that the Dark Powers keep them locked in an endless cycle of torment, but that's more of a kind of resurrective immortality. Instead, we're looking for something that just can't be killed.
Now, it's funny, because built into many stat blocks in D&D is an immunity to bludgeoning, piercing, and slashing damage from nonmagical attacks. In theory, this is meant to fulfill this idea - if you come across something with these immunities, you won't be able to take them down until you find the magic weapon that will allow you to harm them.
The problem, though, is that of the thirteen existing D&D classes, seven of them have access not just to spellcasting, but cantrips that will deal magical damage. So, really, you're only preventing the damage dealt by martial characters, who in my experience will typically make up half or slightly less than half of a D&D party. And then, the moment they get any kind of magic weapon, their damage will work perfectly well against nearly every monster in the game.
This is particularly egregious in the case of monsters that have some specific material they can be harmed by - Lycanthropes and Devils typically have resistance or immunity to these types of nonmagical damage unless you have a silvered weapon, and Golems tend to have these immunities if you don't have an adamantine one. But these idiosyncratic options never really come into play because usually it's just as easy if not easier to get a +1 magical weapon.
So, no, we've got to come up with something a little more robust.
There are two ways to make such a monster "fair" in game terms.
The first is to give the players a way to make them shed their immunities. This would be a little like letting the players find a Lich's phylactery, but of course rather than letting them revive near it, it would just prevent damage going to the creature. Thus, the quest becomes to find the object, destroy it or otherwise deactivate it, and then they can go in on the bad guy.
The other, which I kind of find more interesting, is that there is no way to actually damage them - instead, you need to trap the monster. This would require A: some ingenuity on the part of the players and B: making sure your world has the kind of objects and such that could be used to trap them.
And even though this is clearly a very dangerous monster, we're going to have to take some of our usual tools off the board: we're probably not going to give it legendary resistances, and we're not going to make it immune to things like being grappled or restrained.
And here's another key: we don't want them to do enormous amounts of damage.
It's all a matter of balance. Your players are going to make the fair assumption that if you're throwing this monster at them, they are supposed to fight it, and will likely begin with their standard battle tactics. You're not trying to punish them for their misapprehension - you're here to present them with a novel challenge.
So, here's what I'd suggest: rather than dealing lots of damage, we can imply the creature's enormous strength by instead having big knockback effects. We can certainly have this incur environmental damage, such as throwing a character off of a balcony and making them take the 2d6 bludgeoning for falling 20 feet, but of course allowing for normal reaction-based mitigation like a Monk's Slow Fall or the Feather Fall spell.
But the actual damage of the attack should be... probably on the low end. Naturally, that has different meanings at different levels - 2d8+5 is a huge amount of damage in tier 1 but needs to be coming at you several times per turn at tier 4 to raise anyone's heartrate.
In other words, I think the monster should seem like it wouldn't be that hard to handle... if only it could take some damage. It might take a round or two, when the Rogue's arrows bounce off of it, the Wizard's fire bolt doesn't leave a mark, and even the Warlock's Eldritch Blast isn't making a dent in its HP, but ideally, the party realizes that they can't just get rid of this thing like your typical monster.
Now, what do we do if the party doesn't get the message? I could certainly imagine a scenario in which a Fighter or Barbarian figures they'll grapple the monster and hold on, believing that if they just pick the right damage type they'll finally be able to deal with this thing?
Well, to start with, we're using melee attacks with a knockback. That means that when we land an attack on the person grappling us, we can knock them away and continue the implacable march. That damage might not be a ton at any given time, but gradually, even the toughest characters are going to start taking enough damage that they'll realize that this just isn't working for them.
And if they don't? Well, at some point as a DM you do need to just let players face the consequences of their choices.
What we're trying to get the party to do is to run away from the monster - the successful completion of the encounter is going to be when the party gets far enough away that they aren't being actively pursued (or at least they think they might have lost their tail).
This might be a problem if our players are slower or just equal in speed to the monster. So, we're going to start by giving the monster the following trait: Patient, which means that the monster will not choose to take the Dash action. So, if we give them a standard 30 feet of movement, our players will be able to get away from them if they run.
And, in an ironic way, the knockback effect on our monster's melee attacks will actually secretly be there to help the players - it will let them use an action to dash rather than disengage.
So, to review: the idea here is to make a monster that cannot be defeated (until the plot allows). What extra wrinkles might we add to them to make them more exciting? And what tricks might we employ to let them make a greater impact?
Let's start with our wrinkles.
This is a link to the video that inspired this post. It contains spoilers for a late moment in Alan Wake II, so if you haven't played that game and intend to, and have any sensitivity toward being spoiled, you should avoid the link. As we see in the clip, the monster is capable of moving through solid objects, "blinking" through a wall before ripping a metal bar out of the wall to use as a bludgeon. We could give our monster the same kind of limited teleportation ability to make trapping it more difficult. I'd argue that we should really make sure this is limited, like requiring the monster to see the other side of the wall it teleports through, and likely requiring this to use their full action (possibly their movement and their action). Normally when designing a monster, especially one that is supposed to be a threat on its own, you want to give it as many opportunities for actions as possible (see MCDM's Action-Oriented Monsters). But given that we're not playing fair on the monster's defensive capabilities (being utterly unkillable) we've got to rein in how punishing they can be. Let that moment of "oh shit, the cage we lured it into isn't going to hold it!" be the "damage" the party takes that round.
The next wrinkle to consider is how safe the party can truly be from the monster. Ideally, this thing will show up when least expected. In fact, I think this is the ideal monster to have show up multiple times. To a certain extent, DMs will always be able to contrive ways for villainous NPCs and monsters to always show up to threaten the players. The intricacies of spells like Scrying are sometimes a bit too much for a DM to run through. While you should try to respect the use of things like Mordenkainen's Private Sanctum or other big blanket abjurations, you never want to be so faithful to the rules that it causes the story to grind to a halt (though if you can come up with a way to get around these protections in a manner that doesn't just violate the spells' functions, all the better. A few sessions ago I overcame such a thing by having some Pixies commit a bit of B&E. Did I make them roll to pick the locks on the windows? I don't have to tell you that). So, I think giving a monster like this something like a Revenant's Vengeful Tracker trait could be a good addition to our monster's stat block.
Now, let's talk scenarios:
I think the first encounter with a monster like this, you'll probably want to keep things simple. The players will assume it's a standard monster that they'll fight once, kill, and move past. By becoming this insurmountable foe, though, you can do something like make a location you don't want them getting into just yet inaccessible. That said, they can always run away from the monster by going in rather than running away, so I don't know that I'd even do that. Instead, I might have this be something at a logical terminus. This could be something found at the end of a dungeon, and motivates the party to leave now that they're finished with the place (perhaps desperately closing the front door of the dungeon to stop the pursuit).
As I suggested earlier, having a creature like this show up in an area with verticality will make the knockback effect feel more sinister. Again, we don't want it to be deadly, so probably no thousand-foot-cliffs. But if we find this in the attic of a haunted house (and more and more this feels like an undead monster) we could easily have ceiling beams, landings, balconies, grand staircases, and such that the monster could push players off. Likewise, some kind of sinister stone labyrinth (one with bridges and other kinds of overpasses) would work great.
Given that we can have the party face this foe several times, I'd also recommend that you have it show up at particularly inconvenient times - such as when they're fighting other, more conventional foes. Now, they need to weigh the more immediate, direct, but also "dealable" threat of the monsters they can actually kill against the need to open up some distance with this guy. This could also lend some urgency to a dungeon puzzle (though probably not any particularly challenging puzzle, as that might just make it feel impossible).
Lastly: you probably don't want this monster to be your main villain. A main villain will need to be in some way analyzed and understood. This is the kind of monster where less is more. Sure, if you're going with the "deactivate the thing giving them immunity" route, you might need to come up with some lore and backstory to them, but I highly recommend that this monster remain largely mysterious. Of course, you can go two routes with this as well. The first is one in which the party just never learns much about them at all - the monster shows up, starts chasing them, and the only thing that's important is getting away from it. However, you could also do something that might even be more intriguing: give them a simple, conventional backstory, but one that does nothing to explain why nothing seems to be able to kill them. Just call them "The Iron Knight" or "The Relentless," or an utterly mundane just... name, like "Casper Smotts," and leave it to the players' imagination why this particular person or creature cannot be killed.
I think it's worth noting that the Relentless Killers from Van Richten's Guide to Ravenloft are clearly meant to evoke this kind of trope (there's even a third variant found in Vecna: Eve of Ruin). These monsters do a decent job of this... except that unless you're using them long before the party is of a level to handle a creature of their CR (8 and 12 for the ones in Van Richten's,) and even if the party is theoretically low-level for them, the fight will probably devolve into classic D&D tactics, and then, ultimately, players who know what they're doing will probably be able to take them down.
As another example of where this kind of thing is supposed to exist, but doesn't quite, when I was playing in a Curse of Strahd campaign, we got to the basement of the Death House and encountered the monster there - a Shambling Mound. Despite being CR 5 when the party is level 2, our group (me on a great weapon Paladin, with a Grave Cleric, a ranged Fighter, a Barbarian, and a Fighter/Warlock) managed to take the mound down with relatively little loss of HP. So, while I think the intention of the end of Death House is for the party to desperately flee the dangerous Shambling Mound while the doorways in the upper house erupt into spinning blades (and it actually becomes safer, especially on my 7-dexterity paladin, to smash holes in the walls and deal with the rat swarms that pop out), in our case, there was less direct pressure to move quickly because we handled the monster in the basement already.
What I think this design does is it becomes immune to being "handled." I might even make it so that the only way to ultimately ensure the monster can't come after you anymore is the Imprisonment spell, but we might not need to go quite so far.