Her special stoneskin used to be coded as a spell protection (and undispellable, IIRC), thus breach (which removes combat protections) was ineffective. Try high level spell protection removals: lvl 8 spell pierce shield or lvl 7 ruby ray&khelbens whips. To be honest it has been eons since I played that fight with no mods so I am not sure if it was fixed or changed, so try at your own risk. I always bombard Mel with multiple pierce shields, ruby rays and then a breach or two for good measure and my fighters chop her up fast.
Been a while since i played now, but pretty sure Staff of the Magi and Carsomyr Dispel on Hit works
They are cast at level 30 IIRC, and Melyssan is level 34, which means these dispels have at most 10% chance of working.
I never had the Staff of the Magi fail, but i do have Tweaks Anthology loaded with many options including scrolls cast at caster level, which may also have unintended boosting to the Staff's Dispel Magic. By the time i hit this encounter i'm usually 50/50/50 even as a triple class since i solo.
Comments
the stoneskin she wears can only be removed by your melee fighter hitting her 10 times.