Cerdie uses the spell of Decay, and I haven't found any other counter measure as the genie from the magical box, using his healing - does anybody know the spell or a potion which can be used to break the spell of Decay?

Maybe the Purge spell (Magic of True Faith) could help you as its description says that "This spell purges body and mind of the target of certain negative conditions." - maybe Decay is one of them. And it was suggested by SpecShadow in this discussion that Bless (Divine Magic) should be cast before using Purge to make it effective. I haven't tried that out myself and I don't recall my fight with Cerdie, but maybe it will be helpful.

I can confirm that Purge, at level 12, rids you of Cerdie's status-ailment attack. Just keep an eye on your character's portrait and when it turns green, cast Purge on your character. Cerdie also temporarily reduces your Speed stat, but that's not really a problem, especially if you're a melee character.

I've just defeated her without any Genies by my Paladin, level 53, Olfghard, Diabolus and Jacques de Pulein. I used the Inquisitor sword, some Vidergo seals and the Divine strike, level 18. I tried to use the aforementioned Purge spell, but in my case it's only level 6, and I can't say whether it was effective. Bless and Blade of Fire were also used.
It didn't seem difficult, and she died at first attempt, but she managed to reduce my Constitution by 2. So, I replayed the battle and shot her by Vidergos and 3 Genies.