I think Vienna beats it all: even ignoring variants like Vídeň, Viedeň, Wieden, Wien, Vienna, we still got Beč and Dunaj as obviously unrelated names.
On topic: Rome is Rzym in Polish, and I think they spell Berlin with a y; and of course, they replace l with ł and v with w in Slavic names (Bratisława).
A totally different matter is country names, here it gets real wild: Greece is Ellas/Ellada, Junan(-istan) in Arabic and Turkish respectively, and Grk-, Grek- something in most of Europe. Austria is Rakousko in Czech, Itävalta in Finnish, and Nimsa in Arabic (presumably resulting from a misapplication of Nem'c). Germany beats it, though: Saksaa in Finnish and Estonian, Deutschland/Tyskland and the like in most Germanic languages, Vacija or something like that in Baltic, Alemagne and similar versions in French, Spanish, etc, and Niemcy, Nemečko, Njemačka etc. in Slavic.