Castle Merciless. Home of He who dwells in nightmares.
Just off the craggy cliffs of Corundum, under the rippling blue ocean waves, seven stones stand. They rise majestically from the ocean floor, references to some long ago civilization. Meaningless, now, to all but the most learned.
There are many scret places in the old forests; the least of which is by no means Old Stone Face
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