very next comic, Horace one-shotted the evil cleric using the sword feat that he later teaches Roy. It's implied in comic 600 that the feat is specifically designed to counter spellcasters, so I'd presume there's some bonus damage. Horace is likely higher level than Roy was at the time (over 12th level) and 9th is the minimum for a cleric to cast Plane Shift. So Horace may have at least three levels on the cleric, probably several more.
I'd always just assumed that it was an evil adventuring party trying Plane shift out for the first time (given that the fighter was ignorant of what happened if he killed Roy) and simply bit off more than they could chew. Just because you can plane shift doesn't mean it's a good idea.