I have all characters with 108 Gems equipped (to block Blood Suck), and several with Steal. I use the powerhouses like Orlandu and Agrias to wipe out the Assassins (I always opt to learn Ultima on the gates outside), then I surround Elmdor and Steal, Steal, Steal. Math Skills as secondary takes care of healing.

I have found that Setiemson is by far the best Perfume, since Auto-Haste one of the best positive status ailments in the game.