A Christian brought this argument. He stated that under Islam the polytheist marriage isn't exactly "valid". He stated the fact that the Prophet was born out of a disbeliever makes him a child of adultery (audhubillah). This really disturbed me and I wanted to make sure what the take is. I've already read ahadith where the Prophet stated that he wasn't allowed to supplicate for his mother indicating she died upon disbelief.
The marriages of disbelievers among themselves are valid according to the predominant opinion (Hanafi, Shafi'i, Hanbali). This is evidenced by the following verses about the wives of Pharaoh and Abu Lahab:
وقالت امرأت فرعون
And the wife of Pharaoh said ...
وامرأته حمالة الحطب
And his wife [as well] - the carrier of firewood.
In these verses Allah has called called these women wives of their husbands, and He would not do that if they were not married in His judgement.
Further it is known that when a couple accepts Islam then their marriage is retained and they do not need to remarry. Also their children born before conversion are considered legitimate and inherit from their fathers. This would not be the case if their marriage was invalid.
The Prophet Muhammad ﷺ is born through marriage and not zina.
خرجت من النكاح، ولم أخرج من سفاح، من لدن آدم إلى أن ولدني أبي وأمي
I was born from Nikah and not from fornication, from Adam till my father and mother.
Also on a side-note whether the parents of the Prophet ﷺ were disbelievers is a matter of dispute as some have argued for them being among the Ahl al-Fitrah and have offered alternate interpretations of the ahadith regarding his father and mother.