I agree with your logic but not your premise. Two alien species could effectively communicate if they happened to agree on a shared set of fundamental axioms. The axiom of choice is somewhat contentious here on earth, since it underlies the Banach-Tarski paradox, and it's not clear at all that a sophisticated alien society would have ever accepted the axiom of choice into their mathematics.
This is an interesting thought experiment. The space of all consistent and potentially useful mathematical constructs is gigantic, so I think there would be a good chance that two alien species would share almost no mathematical constructs, and would require decades or hundreds of years to discover - so in this sense, there is a large element of invention to mathematics as a human endeavor.
Even for physics, there are often many mathematical theories that can be used to model the same physical observations (talking about equivalent structures, not about competing theories). For example, many problems can be described equivalently using vectors, complex numbers, or linear algebra. There is a good chance that there are many (perhaps infinitely many) other systems that we haven't thought about that could be used equivalently.
So, while I agree that ultimately the structures in mathematics exist independent of our use of them, so we are only discovering pre-existing structures, I would also say that new mathematical theories are developed using a process that is more similar to invention than to discovery (i.e. you can't explore the space of mathematic theories to discover new ones, as it is infinite in every direction - you can only explore the properties of a structure you essentially invent for yourself).
