Hallo,
mein Kollege hat das noch einmal genauer untersucht.
Das Problem dabei ist, daß Outlook automatisch ein Leerzeichen in die Nummer packt, d.h. die ist dann nicht
+4912345678 sondern +49 12345678
Genau dieses Leerzeichen verhindert das erfolgreiche Wählen.
Es gibt (wenn man weiß, wonach man sucht 
) bei Yealink einen Artikel dazu:
http://support.yealink.com/faq/faqInfo?id=208
Kurzzusammenfassung:
Unter “Features” - “General Information” bei „Call Number Filter“ aus dem ()- ein () - machen (Leerzeichen zwischen ')' und '-').
Damit wirft das Telefon beim wählen dieses Leerzeichen weg und der Verbindungsaufbau funktioniert.
Telefone, die bei uns gekauft wurden haben dieses Problem nicht, da dort der entsprechende Eintrag im Rahmen des Auto-Provisionings gesetzt wird.