Dank eurer Tipps hat sich die Situation gebessert...

Hab' jetzt mal das Fax seitlich mit dem TAE-Stecker an die FRITZ!Box angestöpselt.
T.38 in der Box und Fehlerkorrekturmodus im Fax ausgeschaltet.
Den internen Faxempfang der FRITZ!Box hab' ich auch ausgeschaltet. Das HP Utility am Mac speichert jedes empfangene Fax als TIFF-Bild ab.
Bei zwei von drei Testanbietern konnte ich jetzt ein Fax verschicken (das kann man dann auf deren Webseite betrachten). Bei einem ging's nicht, da stand nur "Keine Antwort" im Faxbericht.
Ein Fax zusenden lassen habe ich mir auch von zwei Anbietern, das hat funktioniert.
Ich nutze übrigens die erste der drei Rufnummern, welche ich von der Telekom erhalten habe, als Faxnummer. Ich denke mal, das macht nix aus, denn es hat ja jahrelang funktioniert.

Ich werd's jetzt mal so belassen. Bei Problemen werde ich dann vermutlich die Faxfunktion der FRITZ!Box nutzen. Oder vorher noch kurz bei der Telekom anrufen.

Ich danke euch für eure Hilfe!