Soweit ich verstanden habe, kann ich grundsätzlich an Legacy-Adressen schicken.
Ja. Du kannst grundsätzlich von jeder Adresse zu jeder Adresse senden.
Das Netzwerk und das Protokoll lässt alles zu.
Das Problem ist nur dass manche Services veraltete Software nutzen und es nicht zulassen an bech32 zu senden. Deren Prüfung ob die Adresse eine gültige BTC Adresse ist, liefert einfach ein "Nein" zurück, weil die seit Jahren nicht upgedatet worden sind.
Von solchen Services würde ich die Finger lassen.
Muss der Empfänger aber auch SegWit grundsätzlich unterstützen?
Nein.
Oder kann ich mich prinzipiell darauf verlassen, dass auch alte Wallets den Geldeingang verarbeiten können?
Definitiv, ja.
Die SegWit-Gebührenordnung (oder wie man das nennen mag) kommt zur Anwendung, wenn die Sendeadresse eine SegWit-Adresse ist, oder?
Sprich, der Typ der Empfangsadresse ist egal?
Korrekt.