Tome of Magic saysAs I recall it's less that they were invented, and more that, with prayer, meditation and offerings, you convince your deity to grant you the new spell. The Tome of Magic points out that Gods can have access to other Spheres and spells than those they normally grant, but in times of need or crisis, can suddenly grant access to their priests (this was done to explain the new Spheres printed in that book, as well as the existence of Quest spells that exceeded the normal power level of Clerical magic).
"The introduction of new priest spheres can pose a logical problem in some campaigns--if an existing Power has influence in a certain sphere, why did his priests never have these spells before? Why do they wake up one morning and suddenly have access to spells never before seen?
The DM can use several solutions to this question. The first is most effective for such esoteric spheres as Thought and Numbers. In this case, few (if any) existing Powers have access to these spheres. Instead, priests arrive (as did wild mages) from distant lands, spreading the word of their god. These NPC priests have strange powers never before seen. In some locations, they may be accepted, while in others, they may be driven out with vengeance. As new player characters are created, this "new" faith with all its advantages and disadvantages becomes an option.
Another explanation, particularly useful for the spheres of War and Wards, is that the Power always had access to these spells, but never had the need to grant them. A deity of war could reasonably withhold spells of the War sphere until the threat of war exists. To introduce the War sphere into the campaign, the DM need only create a little border tension and massing of troops -- the perfect background for many adventures.
Certain deities may be too aloof or remote to become involved in the affairs of men until the need arises. This is particularly appropriate for the spheres of Law and Chaos. A shift in the "harmony of the universe" might warrant the attention of these Powers to "set things right."
The introduction of subdivisions in the elemental sphere can be effected in a similar manner. Foreign priests may enter the campaign region and introduce the concept, or existing priests might discover their own deities suddenly taking a more active interest in their spells. Conflict or rivalry on the elemental planes can be used to justify rigid adherence to a particular element. A fire god, feeling the rising power of a sea god, may enforce strict elemental selection to bolster the devotion of his priests.
Of all the new priest material, quest spells are the easiest to introduce. These are given by the DM only when special conditions warrant. It is easy to justify that conditions have never yet warranted the need for quest spells."
So ToM mostly poses it as a narrative problem of introducing new spells, and suggests some narrative solutions for introducing them. If you have stuff from the beginning there is no narrative problem of new spells.