FrDave notes, in comments on the last post, that the "randomly working miracle spells" approach was tried and rejected in his campaign.
I'm really intrigued by John L's idea and I want it to be attractive to players, even against this experience and my own nagging intuitions. The meat and bones of the cleric, as I've noted before, is healing. 3rd edition D&D recognized this in a big way by making spell slots usable at any time for cure spells. The message is clear. Healing hit points is the number one job of the cleric. Having it succeed only randomly is disconcerting.
So here's a proposal:
Healing: A sacred magic worker can lay on hands a number of times per day equal to his or her level, for healing of 1d6+level hit points each time, with no success roll needed.
All other miraculous powers may be attempted any number of times per day until they fail - at which point faith runs out and that particular power may not be used at all again that day. The basic mechanic is: roll 2d6, success on 9+, 2 always fails, add 1/2 caster's level rounded down and subtract 1/2 the level/HD of the opposition rounded up. Apply the cleric's Wisdom bonuses as per your system. In classic John L style you can see these as reaction rolls where 9+ is a favorable reaction, or morale rolls where 9+ is broken morale of the opposition. This is really more for memory than mechanical purposes though; the cleric's Charisma does not come into it.
Curing conditions: disease, insanity, injury, sorcerous influences. Use level of the spell's caster, HD of creature originating the condition, or 1/3/6/9 HD for mild/moderate/serious/death. You may rule that repeated attempts by the same cleric on the same condition are not allowed.
Banishing evil: turns unholy creatures and gives an immediate morale check to other evil creatures. Use level of one creature to check, numbers over that turn additional numbers of creatures. Yes, this is a less impressive turning power than normal, but I feel it's balanced when you add on the healing and the upgrading of other at-will powers, and the morale effect.
Of course, other powers may be added on, but I think this short list has the benefit of being fairly well balanced against the magic-user's powers (4 rather situational abilities with a starting 1/3 or so chance of success), and has an impeccable cultural pedigree.