I tend to find synergy with classes that others don't, maybe because I'm delusional or something, but rogue and cleric works imo. A high wisdom boosts casting and spot, and the find trap spell is great for making up for cross-class skill points spent on search.
Cleric+Rogue is an option that allows for traps, UMD, and with 2 or more levels evasion (as stated before only good with a high reflex)
Cleric+artificer allows for xbows, UMD, trap skills, an iron defender that can pull trapped levers, and the force enhancements that add to the damage of blade barrier.
Two multiclass cleric builds I've played with are:
18 cleric/2 artificer (Holy Gun) allows for traps skills, UMD, xbow damage, rune arms, and heavy armor (even better with the last update to damage reduction)
18 cleric/1 artificer or rogue/1 monk or Wizard. this would be a caster build, and uses the free feat from the monk/wizard for either toughness or a metamagic. the artificer would give xbows, traps, UMD, and the force enhancement, rogue gives more skill points)
For the record I've never been kicked from a party, or denied a slot for using a multiclassed cleric. Maybe I'm just lucky, but I've only heard of it on the forums. Maybe this is an issue for higher level content and raids though. I will say that being able to find and disable traps as a cleric has landed me in a number of parties though, as those are the 2 things most commonly asked for in a party in my experience.
If you use evasion you would have to use robes or light armor, but you can use large shields too. Shields can have nice enhancements on them, and add great damage resistance. But in my experience the items I found with the most beneficial enhancements for my cleric caster were quarterstaves, so maybe a monk splash wouldn't be too bad. (even if you don't use evasion, the free feats can be used for toughness, power attack, lightning reflexes, etc.)
You can also lesser reincarnate for free, so you could play as a melee for the early levels, and LR later on to be a caster (I did this with my cleric)
Hope this is helpful, and not just a pile of unnecessary poo...
-PaxsMickey
EDIT: Another fun build might be 16 cleric, 2 paladin, and 2 rogue. For that build you would want a decent charisma. The charisma would boost your saves, making evasion useful, while also giving you more turn undead for your burst heals (the primary source of healing for me when I played cleric) Feats are tight for this build though, and the casting would be weaker, so it would be more for support. When I quest I want the last one standing to be able to revive the rest of the party, and the cleric can do that.