We try to take considerable care in kerning our Arabic fonts, including those we work on for other foundries. Obviously what needs attention are right-joining letters followed by isolated or initial letters within words. In some calligraphic styles, kerning across word-boundaries is also desirable where swash final forms dip under following words.

What I think of as the basic kerning of Arabic is fairly easy to do, but gets more complicated when text contains vowels or other marks: then kerning can result in situations in which either the mark positions need to be contextually adjusted (traditional technique based on scribal practice) or the kerning needs to be contextually adjusted, or both. The Adobe Arabic fonts that we made for Adobe use a combination of both mark and kern adjustments depending on context.

Sometimes the budget for a project is such, and the expecation of vocalised text so limited, that we can't afford to spend much time on contextual adjustments. Because most Arabic text does not use vowel marks, there are seriously diminishing returns to the large amount of work required to define all the contextual adjustments. Some clients balk at the cost.

(1) Are there any typefaces that do this well?

I write one with 5553 kerning pairs (and also increasing). see my post on this forum.

(2) What the kerning pairs that need adjustment?

1 - all of [right-joining characters [isolated and final]]+[dual-joining characters [initial and isolated]]
2 - all of [right-joining characters [isolated and final]]+[right-joining characters [isolated]]

If you want to design an Arabic font with kerning, you have to be careful of above marks. you can add an extra substitution for replacing base glyphs with their alternatives when above marks are applied.
My advice is not to try make pairs manually. if you want a completed and clear kerning, write a program to accomplish it. i write an algorithm using some artificial intelligence and image processing algorithms to make kern feature in form of VOLT lookup.
I can send you the algorithm.

(3) What software do people prefer for working with Arabic script fonts?

I'm not a professional font designer, but I'm pretty sure VOLT+FontLab+Font Creator is necessary and enough for designing clear Arabic fonts. you could use AFDK too.

Soroush, your kerning algorithm sounds very interesting, and I would like to take a look at it. If it seems useful, I'd also be happy to discuss paying your something. Please contact me at tiro[at]tiro[dot]com