Guys, learning Latin (or at least Italian/Spanish) never hurts :)
With some exceptions (like "mężczyzna", "sędzia", "oferma") those words were borrowed from Latin, where they also presented this irregularity (-a ending and male gender).
Since this combination isn't natural for Polish, so the rarely used words (like "asteroida" or even "planeta") switched to the common sense gramatical gender quite smoothly.
Trying to change the gender of "mężczyzna" to female (because of -a ending) would be much more difficult :)
Originally it was "mąż" for a man (today "mąż" = husband), I don't know why they applied the typically female ending to it (or more precisely to the adjective "męski" = manly, you may find the ending -yzna in other words, "ojczyzna", "ojcowizna", "£emkowszczyzna", "golizna", "blizna", "łatwizna" etc., they are always femele gender).
Quite an ironic fact in Polish is that the word for 'man' - 'mężczyzna' has an ending typical for feminine nouns.
Well, in German "das Weib" (a woman) and "das Mädchen" (a girl) both have a neuter gender, so Polish isn't the only language with such "problems".