I think the entire idea of decay is ... unsavory. I feel that the best way to keep interest in the game is to give more power to the player, albeit in rather small quantities.
I propose the idea of having the current set of spells, with an elaborate upgrade system.
Similar to rare commodities, certain enhancements to the spellgems become available at various civ levels. These enhancements are created from objects that originate from the caverns. A similar system could be used - the gem veins drop a single stone of their element for use in creating new spells, but the gem dust varies by mark. The gem dust can be used to create upgrades for your spells, in conjunction with various other commodities such as iron or magma. The gem dust can be broken down into lower level gem dusts to allow for the creation of weaker upgrades if it is desirable (in some cases, it may be).
These upgrades can vary by mark, and are not all available at the beginning. Each upgrade is reusable; if you create a new damage enhancement II, you can still use the tier 1 version of it on another spell. Each spell can have a limited, but raisable cap of "slots". This cap rises with the civ level, and nothing else. This cap increases quickly in the early game, but slowly falls off as the game progresses, to a minimum wait time between increases. This allows for a relatively balanced game throughout, because even if a person has a fireball with a dozen upgrades, he can only use a few of them on a low civ level server.
The number of slots each upgrade uses is dependent on the effect of the upgrade and the tier of said upgrade. However, you can't equip two kinds of the same upgrade on the same spell, so you can't have a damage +50% and a damage +25% on the same spell. However, you'd be able to put a damage +25% and a cooldown -25% on the same spell. These things, of course, should not increase linearly. The lower mark upgrades are more efficient, but prevent further exploration into that area, so it is possible to have a super spell that isn't very well rounded, or instead a spell that isn't too powerful, but has lots of different effects.
For example: The player goes out and gets ruby dust II, which he can use to make a +Damage II upgrade, but he does not have enough slots. Instead, he decides to use this ruby dust II to make two ruby dust I's, one of which he makes into a +Damage I, which he happily puts on his spell. Several civ levels later, he has more slots and decides that he no longer likes his old +Damage I upgrade, and decides to go gem hunting again. He gets his hands on a sapphire dust I before getting bored. However, he can't make better upgrades with just a mark I dust, so he makes a new upgrade, +Cooldown Reduction I, and sticks it onto the spell with his former upgrade. His spell, in addition to having the extra damage, now also has a shorter cooldown. Later, he gets tired of this again, so he gets his hands on another ruby dust II, now making it into a +Damage II upgrade, which he replaces the two previous ones.