echo $begrüßung;

Ich habe leider feststellen müssen, daß die Sortierfolge von MySQL und PHP dann unterschiedlich sind, wenn am Vergleich deutsche Umlaute beteiligt sind. [...] Hängt das mit dem Zeichensatzcodierung zusammen oder gibt es da einen Workaround?

Nein, der verwendete Zeichensatz ist dabei unschuldig. Für die Sortierung ist die Kollation zuständig. Wenn nichts anderes konfiguriert wurde, sortiert MySQL schwedisch.
Das Thema Zeichensatz und Sortierung wurde in MySQL 4.1 stark erweitert, so dass nun an vielen Stellen einzeln Zeichensatz und Sortierung eingestellt werden kann. Wie es vor Version 4.1 war, habe ich mittlerweile vergessen, ich glaube aber nicht, dass das anderswo als in der Serverkonfiguration einzustellen ging. Das online verfügbare 3.23,4.0,4.1-Handbuch geht auch nicht weiter darauf ein (oder ich finde die passende Stelle nicht). Alte Handbücher sollten aber noch in alten Download-Paketen vorhanden sein, wobei gilt: je neuer die Versionsnummer, desto höher die Chancen schon das Handbuch der Nachfolgeversion zu erwischen.

echo "$verabschiedung $name";