Others have already linked to the Wikipedia article on “Namen auf -ow”. I’d like to add that your hypotheses were basically right, except regarding Old Prussian: Old Prussian was a Baltic, not a Slavic language, although both are closely related; and it was spoken further to the (North-)East.
In general, place names tend to be quite sticky; the people that live in a place may change, or their languages, or both, but the old name for the place continues to be used in most cases. It is just adapted in pronunciation and spelling over time.
A somewhat related example from the English-speaking world are place names ending in -cester, in England. They derive from the Latin word castra (fort) and have survived until today, in spite of the relatively short Roman presence there and of the language transitions since. Their pronunciation (or their spelling, depending on how you look at it) is regarded as unusual, as well: Worcester [ˈwʊstə].