It's not too difficult; people would normally be distinguished by patronymics formed from bin or ibn or some nickname referring to their geographical origin. For example Muhammed ibn Ishaq, the author of a famous biography of Muhammed, is usually known simply as Ibn Ishaq to avoid confusion. A further example is furnished by for instance the name Amhed, which is shared both by a ruler of the Tulnid dynasty known as Amhed Ibn Tulun or Ibn Tulun or the jurist Amhed Ibn Hanbal.

Just to add to /u/farquier there's also a tradition, particularly in Egypt, of naming a son Muhammad but then calling him something else.

So Hosni Mubarak's real name is Muhammad Hosni Mubarak. Anwar Saddat's full name is Muhammad Anwar al-Saddat. Yasser Arafat (born in Egypt) was born Muhammad Yasser.

etc. etc.

Even in Egypt though no one calls them by their full names.