“ 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 discover an ancient, dusty oil lamp, somewhere in the bowels of a dungeon. Naturally they 'rub it', and out pops a wizened, old djinn. So far so good. Then it speaks...
'Ah at last, at last I am free! Now grant me my wish!'
When the PCs explain that they are the ones that should be granted a wish, the malignant djinn explains to them that his particular oil-lamp has a curse placed upon it. Whomsoever releases the entity inside shall be geased to grant the djinn's wish to the best of their ability.
Groans ensue from the party. The djinn rubs his wrinkled hands, grins, and proceeds to name his wish. What could it be?”
“ What if you send the players in a dungeon that was already raided? Maybe you could have traps that are already set off, or the corpses of monsters etc.”