I've been wondering this for a while now. The second half of Alexander the Great's name looks very much like the genitive singular of ανήρ re-interpreted as a second-declension nominative singular. Is this indeed the derivation, and if so, is such re-interpretation common in compounds involving ανήρ?
The phenomenon of -andros being used in compounds is clearly common, but I disagree with your explanation of it. It is the anhr form of the noun that is the irregular one and it is normal for compound words to be formed on the root rather than nominative. For example compounds of pas are pant- and there are many other examples. The root of anhr is andr, so those are the consonants used in the compound. -os is just a noun ending that happens to look like the genitive of the original noun.