“ 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 nations of the Kolm surpasses all other barbarians in their wilderness of life. Thoug they do just bear the likeness of men, of a very ugly pattern, they are so little advanced in civilization that they make no use of fire, nor any kind of relish, in the preparation of their food, but feed upon the roots which they find in the fields, and the half-raw flesh of any sort of animal. I say half-raw, because they give it a kind of cooking by placing it between their own thighs and the back of their horses. They fight in no regular order of battle but by being extremely swift and sudden in their movements, they disperse, and hen rapidly come toghether in loose array. They spread havoc over the vast plains and flying over the ramparts, they pillage the camp of their enemy almost before he has become aware of their approach. They are the most terrible warriors for when in close combat with swords and flails they fight without regard to their own safety, and while their enemy is intent upon parrying the thrust of the swords, they will entangle him with their chains so that he loses all power of walking or riding.
Excerpt from 'The peoples of the world' By Taklamarian court-scholar Guliman Amon.”
“ The Yugzhee, or 'hedgehog-people', guard a great, secret treasure inside their giant burrowed lair. The mysterious Wall of Keys, a 12'x10', foot-thick, cold-iron, 'wall', upon which, on iron hooks, hang 100 ornate iron keys of all shapes and sizes. Each key opens some heretofore un-openable barrier, door, or gate, in the particular game world of choice.
The PCs have come upon a great boon, except for the fact that the keys cease to function properly if separated from the iron wall for more than a few minutes. Higher level characters will be able to figure out how to take the wall 'with them' via magic. Lower level characters will have to get creative.”