I forgot to mention how I would actually handle applying the Moldvay principle to the cleric.
Firstly, I would not require the cleric to keep a spellbook, nor study to regain spells. They would need to spend an appropriate amount of time in meditation/prayer, following proper rest.
Secondly, they may only "know" a number of spells equal to their spells slots available, +1 per spell level, if Wisdom is 15+. For example, a 4th level cleric with a Wisdom of 16 would know three 1st and two 2nd level spells.
Thirdly, they may cast any spells they know, in any combination, up to the number of times listed for their level. This is not adjusted for Wisdom. So, the cleric in the example above could cast two 1st and one 2nd level spells. They do not have to prepare them ahead of time.
Fourthly, the cleric's spell selection should be based on player choice, broadly influenced by deity. Detailed pantheons aren't strictly required. It should be a simple matter for a player to declare that his cleric is devoted to a god of battle and choose spells loosely based on that. Once chosen the selection may only be changed when the cleric gains a level. At that time, the cleric may change one spell per spell level. So, the cleric above could change one 1st and one 2nd level spell upon attaining the 5th level.
At the risk of sounding immodest, I am pretty happy with how this reads. Of course, playtest may reveal problems, but that's a horse of another color.