My top graphviz issues.

* Automatic edge placement can lead to visually ambiguous results and it is very hard to tweak it.

* Edge title placement engine is sort of naive and best solution is to not use edge titles at all.

* Bogus text wrapping. Text can leak outside of the node box.

* Default margins and padding lead to visual clutter.

I was about to summarize my pain points but you covered them all and expressed them better than I could. What I often find difficult is to reliably prevent overlap, I would subsume that under you last point about margins and paddings.