Magic only works that way for Paladins. Clerical magic doesn't work that way. Clerics just have to say that they're a cleric and *poof* they get magic — and, to top it off, all of the clerics in the known world get the same magic with only minor variations (regardless of what god they worship). Further, you can learn powerful magics (arguably more powerful magics) in D&D without worshipping a god. This is what I alluded to above.
Clerics might all get the Cleric spell list, but they do have different Domains (or Spheres depending on your edition), and those can have some nifty spells and granted powers in there well above what Clerics might normally get. Death Touch for the Death Domain, Disintegrate and a 1/Day Smite Anything for Destruction Domain, Time Stop and Bluff, Disguise and Hide as class skills for Trickery Domain. Madness domain lets your Spell DCs and bonus spells go sky-high, but at the cost of going pretty much totally insane (effective permanent Wisdom penalty of half your cleric level to everything except spellcasting, effective permanent Wisdom bonus of half your cleric level to spellcasting). Admittedly Evil domain is pretty weak, but there are lots of domains Evil deities can offer that could be tempting.
As for temptation by power. I could see a nice temptation going by a high level Evil Cleric making say, a +5 Unholy Flaming Ghost Touch Adamantine Longsword, normally a list price of 165,315 GP, costing 82657.5 GP to make. Imagine selling it for the low, low price of 90,000 to some young up-and-coming adventurer who just came into town with a big haul of loot or the word is out is looking to buy a new sword? Nice sword, it comes real cheap if you'll just accept the teachings of Loviatar and it can be yours. Ooh, looks like it's hard for you to contain the awesome power of that sword (i.e. the negative level because it's Unholy), we'll give you our special blessings so you can wield it, just repeat those teachings as we lay our hands on your (and cast Atonement/Temptation). C'mon, come to our party tonight, and just think how much damage you can do with that sword now (that you just changed your Alignment to Evil so the sword won't hurt you when you hold it and you effectively sold his soul for about 75,000 GP, and is beholden to dark deities and on the quick path to being a minion of evil). . .
In other words, the ridiculous profit-margin markup of magic items is some place I could see evil religions using as a sales ploy by deeply cutting the markup on items that you have to be Evil (or a member of their faith) to use safely.
In some D&D settings there is no getting divine spells without a patron deity, end-of-story. Forgotten Realms is one. Dragonlance for most of it's history, before the discovery of the Mystics in the 5th age, is another one. The whole plot of the original Dragonlance modules and novels was that without real Gods to worship there was no divine magic to be had.
While it was de-emphasized in 3e, in 1e and 2e it was quite crystal-clear that a deity could revoke a Clerics spellcasting if they displeased him. It isn't simply declaring that you're a cleric of GenericGod and keeping appropriately close to his alignment, it was upholding the tenets of the faith because every day when you pray to rememorize spells you're essentially asking your God for resources to keep on doing what you are doing and if he doesn't approve, No Spells For You.