Ich würde Umlaute und Sonderzeichen ersetzen (ä => ae, ß => ss, etc.) und gleichlautende Namen per Nummer unterscheiden. Ähnlich wie es XING macht: https://www.xing.com/profile/Juergen_Gutsch2
Das 1.Problem ist eigentlich nur dann ein (technisches) Problem, wenn die URLs nicht korrekt codiert werden. OK, die korrekte Codierung von Mößlitz (M%F6%DFlitz) ist nicht mehr unbedingt sprechend, aber eine Umsetzung als Moeszlitz sollte programiertechnisch keine Schwierigkeit sein.
Für das 2.Problem (Nichteindeutigkeit) gibt es neben der künstlich erzeugten Eindeutigkeit durch anhängen einer ID, PLZ, Gebietsname, etc. noch die Auflistung und Auswahl der Stadt auf einer Zwischenseite, bei Aufruf eines nichteindeutigen Städtenamens.
Problem 1: Man könnte entweder in der mod_rewrite Anweisung die Sonderzeichen über einen entsprechenden RegEx Ausdruck umschreiben oder, was einfacher wäre, man gibt die Städtenamen einfach vom System her vor. Zu München würde dann eben keine Seite existieren, sondern nur zu Muenchen. Zu dem mod_rewrite-RegEx Gedanken ist es vielleicht auch nicht verkehrt, sich mal das MediaWiki näher anzugucken, da gehen die URLs nämlich mit öäü und - und so.
Problem 2: ist in der Antwort von FalkP schon hinreichend abgehandelt. Das mit der Auflistung und Auswahl auf einer Zwischenseite, bei nichteindeutigen Aufrufen, macht MediaWiki übrigens auch so.