“ Rather than making a baddy impossible to hit, consider giving it mega-hit points.
Super hard to hit leads to great player frustration. Allowing them to do damage leads to a sense of accomplishment. another variation of this would be to give the bad guy a forcefield that shows damage.You could also give them a mastermind ability that sluffs the damage of to minions who should be easy to kill.Once in a while a super high to hit encounter is ok ,but it should be few and far between.
Your mileage may vary”
“ The PCs are hired by undead to rid their village community of an invasive necromancer.
As the PCs make their way, wherever they are going, they spot two zombies. The zombies approach but before the cleric can turn them, one starts throwing coins at the PCs while the other pleads with them, unable to pronounce the letters 'L' and 'H' due to some missing gums. 'Peeth issen...no 'arm...coin...peeth issen!'
If the PCs don't slaughter the two zombies immediately, they will eventually come to learn that the two were chosen to find help by their brethren. The zombies want to hire the PCs to rid their community of an unwanted pest. An opportunistic necromancer.
Apparently, a small benign community of undead have taken residence in an abandoned village, living out their undeath as peacefully as the undead can. Recently, a malicious necromancer has invaded the village, and plans to enslave the entire populace with his malignant spells, raising a small army.
The PCs must battle the vile necromancer, even as he animates the very folks who hired the PCs in the first place, to slaughter them.”
“ The monarch used to have absolute powers until the disappearance of King Henry V. A 'temporary' replacement was put on the throne to hold it until King Henry returned, and he would have only one vote on the governing council of nobles and no other powers except persuasion. More then 50 years have passed since then and everyone knows King Henry is almost certainly dead-but the nobles don't want to go back under the rule of an absolute monarch, so the kingship is only 'temporary' until King Henry V returns to take back his throne.”