As others have said, it doesn't seem like there's too much of a problem here. Your players roleplay their characters well. They know the rules and don't generally abuse them (although they do find nifty synergies within them). And they like to play the same kinds of characters. What's the problem with that?
If you want to encourage diversity in PC class choices, try a few other things before punishing the PCs for playing clerics.
Look into allowing use of the Favored Soul from the miniature's handbook. It's a bit like a cleric but some players might like the idea of spontaneously casting from the cleric list.
Restrict the availability of NPC hirelings--and/or their trustworthiness. Hiring an honest rogue isn't that easy.
Consider adding a little extra to other classes. Use the exotic weapons from Complete Warrior and give fighters a bonus exotic weapon proficiency at level 2 or 3. (You might want to do that at level 2 and move the lvl 2 bonus feat to lvl 3 or even give it at level 1 and move the bonus feat from 1st level to lvl 3 so that characters can immediately start using their weapon of choice). You could also take the Exotic Weapon Master Stunts from Complete Warrior and make them Fighter bonus feats with prereq: Fighter lvl 6.
Consider giving paladins a bit of a boost too. Maybe Divine Might as a bonus feat at seventh level or something. Or Divine Vigor as a bonus feat. Heck, you could give paladins ALL of the divine feats from Complete Warrior (except Divine Might and possibly Divine Shield) without overbalancing them too badly. (Because most of the divine feats are of very limited use).
You could try using the 3.0 Uncanny Dodge progression for rogues. And maybe give rogues organizations (to keep the same party focus, you could use organizations like: the Eye of Lathander (secret organization dedicated to Lathander that infiltrates and gathers info on evil groups) rather than the Sopranos guild of Waterdeep) that grant them bonusses to some skills (Gather Info, Use Magic Device (for cleric items), Search, Sense Motive).
You could go back to the 3.0 opposition schools for non-necromancer wizards or even give wizards specialization without ANY barred school. (Nobody would play a generalist, but is that a problem?) You could also use the domain sorceror Vrylakos and I developed years ago to make sorcerors more interesting
http://members.tripod.com/vrylakos/classes/sorcerer_domain_system.htm
Or you could emphasize some of the combat aspects that tend to give clerics trouble:
-Reflex Saves--Fireballs, Lightning Bolts, etc. But also effects like Otiluke's Resilient Sphere and Grease.
-Dispelling. At high levels (when buffed clerics get really good at melee), everyone should pack dispel magics. Give your bad guys Dispel Magic, Greater Dispelling, and Chained Dispel Magic spells (target all of the PCs with one spell).
Alternatively, when starting a new campaign, you could give it a very strong story hook: The king of Goodjustlandia is sending out parties to quest for the Holy MacGuffin. You are one of those groups. Selected and balanced by the king's trusted advisor, your party will have: A cleric or favored soul. A fighter or paladin. A rogue or Fighter/rogue (use DMG option for 1st level multiclass), ranger, or ranger/rogue (1st level multiclass). A wizard, sorceror, warmage, or bard. A bard, fighter/wizard (1st level multiclass), or marshal. Let the players decide which role they want to take on.