Oddly, the city in Virginia is not named after the city in Egypt, but after an Alexander family that owned an estate in the area.
In another thread about cities named after people, I investigated other Alexandrias in the US and found that most of them were actually named after founders or local families rather than the city in Egypt.
I do feel embarrassed by the fact that my nation can’t be bothered to actually think of a new name, so borrows names of foreign cities, and then makes up the most awkward pronunciations. I mean, besides Cairo = KAY-roe, we have Moscow, Idaho = MOHS’-ko? Rio, Wisconsin = RYE’-oh? And Des Moines (outside Seattle) = Dezz-MOYNZZ’…
Really?
And I acknowledged that. I also included North African and Middle Eastern places.
Corpus Christi (Texas) means “Body of Christ” in Latin.
Baltimore (Maryland) means “Town of the Big House” in Gaelic, and was named after the town of the same name in Ireland.
Anaheim (California) means “home of Ana” in German.
Ohio has both Mecca and Medina.
It was actually named for the Cecil family, who were Lords Baltimore, who derived their title from the town in Ireland.
ahem, no, its MOSS-cow Idaho, a college town.
Isn’t it MOSS-Ko?
There’s a Moscow Md. that the locals used to insist was pronounced MOSS-Ko just because of the association of the name with the USSR. Or so I was told as a child, never been there and actually heard it pronounced by a local. I believe it was college town as well. Probably a medical school at the local butcher shop 
Along the same lines I’ve been told there is city of Berlin someplace where they pronounce it BEAR-Lin for similar reasons. All hearsay though.
These are both European, but last week we were driving back to Nashville and drove through, consecutively, the communities of Carthage and Rome. I wondered if the high schools were bitter rivals, maybe the Carthage Elephants and the Roman Legion locked in annual battle on the football field.
Carthage was in North Africa, near to where modern day Tunis is.
There’s a Helen, Georgia and a Hell in Michigan.
:smack: I knew that. I was more amused that those two classical superpowers of antiquity were right next to each other in rural Tennessee.
Melbourne FL is named after the city in Victoria, Australia.
Brisbane CA may or may not have been named for the city in Queensland.
Any others named for Australian places? There’s several places named Perth, but they seem to be named after the original in Scotland.
Colorado has No Name, and Nowhere.
Actually, we usually say “Deh Moyn”. (Not that it’s much better than Dezz-Moynzz)
Some more that have occured to me. Mostly from the classic/ancient world.
Babylon – in New York
Bagdad – several unincorporated places. Note difference in spelling from Baghdad, Iraq.
Damascus – several, MD and OR are the two largest.
Nineveh – several unincorporated places named after the ancient Assyrian city.
Smyrna – several, largest of which is in Georgia; named for the ancient city in Asia Minor, now known as Izmir, Turkey.
Thebes – in Illinois, named after the one in ancient Egypt. (I couldn’t find one named after the one in Greece.)
My current home city, Denver, was named after some dude with an English name, IIRC in order to impress same dude. Maybe a barrel of whiskey was involved? Probably, because Wild West and what not.
. . . which is named after this guy, whose title was named after this place, which is in Europe. So, not really the “non-European origin” that the OP is seeking.
Named after a river which was named after Thomas Brisbane, who was a Scot.
The OP specifies the origin of the name, not the immediate antecedent. There are lots of Australian places whose names orginate in Australia, but neither Brisbane nor Melbourne are among them.