There are quite a few pre-Islamic taboos some of which persist to this day. For example, can't give a child a name of a living person parents know of. This of course includes extended family, friends and even acquaintances. This restriction alone enforces creative naming.

Typically names consist of 1-5 elements which can be combined arbitrarily. There are literally thousands of such elements though.

Last name often is a first name of an ancestor a few generations deep and it is likely to be unique too.

So as a result first+last name combinations are quite unique.

Urbanization is changing all this of course but some traditions are still strong. In my entire life I've met just 3 people with the same first name as mine.