The Megillah was clearly referring to the future name of Yathrib. This is a normal occurence, like we see in Kesubos 10b, where the Gemara says that the city mentioned in the Pasuk in Bereishis is referring to the city that in the future will be in that site:
ומי כתב קרא לעתיד? אין, דכתיב (בראשית ב, יד), ושם הנהר השלישי חדקל הוא ההולך קדמת אשור, ותנא רב יוסף, אשור זו סליקא. ומי הואי? אלא דעתידה - Does a Pasuk refer to the future? Yes, like it is written- " The 3rd river's name was Chidekel, it went towards the east of Ashur." And did Ashur exist [at the beginning of creation?! Rather, [it is referring] to the future.
As for why it says there were 127 Medinas, well, I think you're just reading the Pasuk wrong. It really should be read like this:
הַמֹּלֵךְ מֵהֹדּוּ וְעַד־כּוּשׁ שֶׁבַע וְעֶשְׂרִים וּמֵאָה - Who ruled from Hodu to Kush, 127 [provinces]
מְדִינָה [and also] Medina.
Why was Medina mentioned specifically? I don't know. Maybe because it was a big city, or because of its importance to islam. Who knows? Maybe it's mentioned for a Derasha to teach us that Achasverosh ruled over Medina, which is a capitol, like his own capitol.