My point being that his beliefs were watered down and altered by the peoples in that region, so some of the ancient people's practices are still used today.
It's no different from the pagan customs that were introduced into Christianity by the pagans. Christmas trees, mistletoe, Easter (Ishtar) bunnies, etc. etc. All beliefs become corrupted at some point.
None of those. His religion was partially founded on obliterating the idol religions, otherwise it was a blend of Christianity, Judaism and an effort to right some of the wrongs he saw in the culture. Some of his culture of course came into it, but he completely rejected any of the idol religions.
Aside from that, Islam did spread far, and into lands where people did not entirely give up their local religious practices, such as female circumcision.