I'm ran holy paladin/disc priest at the start of the season, and now run disc priest only. We are currently at 1740 and rising fast after ~2 weeks of seriously "working" on the team.
(my team is full deadly equiv - unbuffed: 22khp, 2200-2500sp, 900-930 resil)

To be honest the only thing I miss is Aura mastery, and I dont miss it that much: aoe stuns shut you down in 5v5, not interrupts, making AM almost useless. The priest however has been great. Aoe healing is very nice, PS for focus shielding works great and is tough to dispell. My priest even discovered that holy nova makes a good addition to his healing rotation once the cooldowns and burst have subsided. Aoe fear is ok, mainly we've found it useful for Ring of Valor to disrupt their opener and give me ~2 secs clear firing range to LB/CL/FS my first Gib target (never open with the kill button).

Against Cleave comps, which are obviously very tough for us, I have just been VERY patient with my opener. I will gently TS 2-3 times bouncing them off me a few times before doing much of anything. This really helps disrupt their rythmn and lets some of their burst + CDs die off. My priest drops a scream in here somewhere(usually trinketed), at which point I can TS+Earthbind and get my first clear shot. This all looks good on paper and in reality i am getting Feared/shadowfury spammed, but it has worked better than trying to go balls out. Keep your damage abilities until after they blow their AOE CC, only then can you get a good combo off and actually kill anyone. The more relaxed and patient I have been with my abilities (instead of instinctivly OMGWTF spamming TS), the more these matches have started to make sense and I could actually start getting practice.

Kill Order: I have found with 2healer/cleave comps, warriors and DKs are too resilient to out dps the healers, and its too dangerous to waste ur kill button on these guys, so I have started gibbing one of their healers now, and its working great. I bounce them around with TS to mitigate the initial melee burst, drop a healer, and then (if applicable) blow the rogue up who is guaranteed to be sitting on my priest. With 1 healer up and melee having lost much of their cooldown advantage, you will have a super easy time dropping the melee juggernauts with a one of our many 3 button kill combos.

With that last comp you mentioned, I think the strategy is similar. Pull them back away from the pillar if possible by bouncing the melee around with TS. Ghost cast on the melee (LB/CL), draw the healers out, then TS and drop one of the healers. As stated above, DKs and Wars are far too resilient and beefy to out-dps 2 healers, let alone 3. Get 1-2 of those those healers down and those melee become cake. I have started ignoring warriors all together until almost last, and its worked well. They are a sponge and a distraction. Kill them once, and the rest of the night they'll sit in sword/board 90% of your matches, making them useless anyway.

As far as high rated kill targets go in general, it is becoming more and more difficult to fake out the healers and get kills off (unless its druid/shaman/rogue after CoS which are all very soft) which SHOULD be the case with good healers who are watching your target switches. For this and other reasons, I have not yet, but have been meaning to create a focus based kill macro which I know has been mentioned already by some of the other arena boxers here. This will help immensely against these comps, focus the priest/druid healer, throw some LBs at the warrior then BAM healer down.

Hopefully this helped it can be tough to put arena strats on paper, as they are such a random zerg fest nowadays. Bounce some more questions and let me know what has been working for you if anything.

Good Luck!