je vous ai parlé / je leur ai parlé (richtig)
j'ai parlé avec vous / j'ai parlé avec eux (variante etwas umgangssprachlich)

Danke!!!

Ich habe Sie angesprochen und niemand anderen.
Ich habe mit Ihnen gesprochen und sonst niemanden.

"parler avec" ist gar nicht umgangsprachlich.

Beispiel: "Je parlais avec des amis sur le trottoir lorsque c'est arrivé" ist so weit ich weiss 100% korrekt.

Der Unterschied zwischen "à" und "avec" ist eher dass "avec" eine Kommunikation in beiden Richtungen hindeutet, wie auf Englisch (talk to/talk with).