The Shadow Thieves. I am a Paladin...and they seem less evil.

Right. Unfortunately, unless you've completed all the quests for the thieves (which seems unlikely given your level), you don't yet have access to the mace that Armen was referring to. Hopefully some of the other tips posted here will help you.

Give'em hell.

Or, if you've rescued Trademeet from the Genies(sp?), you will receive the Shield of Harmony +2 which will give you immunity to charm, confusion, domination, and hold person. Perfect for Minsc, don't you think?