“ 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”
“ A caravan is traveling through the desert. The party is hired to capture a man who is in the caravan, and it must be done quietly, so that nobody else knows. They are given the man's name, and the fact that he is a mage, but no other information about him. The catch is that the caravan consists of ten wagons, with at least thirty or forty guards.”