All perfect praise be to Allah, The Lord of the Worlds. I testify that there is none worthy of worship except Allah, and that Muhammad is His slave and Messenger.
The saying that the Niqaab (face covering) did not exist at the time of the Prophet is not true, and we do not know any scholar who said that it did not exist at the time of the Prophet and that women did not wear it, although they (the scholars) differed in opinion whether or not it is obligatory.
Among the Ahadeeth that prove that the Niqaab is obligatory is the saying of the Prophet to the woman in a state of Ihraam for Hajj or 'Umrah: "A woman in a state of Ihraam does neither cover her face nor wear gloves." [Al-Bukhaari]
Besides, ‘Aa’ishah narrated: "Riders would pass by us while we were in the company of the Prophet in a state of Ihraam for Hajj, so one of us would draw down her outer garment from her head over her face, and when they had passed us, we would uncover our faces." [Abu Daawood and others]
Also, it is not correct to infer from the story mentioned in the question that the Niqaab did not exist because the Niqaab was not made obligatory at the beginning of the Prophet's era, as the Companions used to see the women and recognize who they were, and then the legislation of the Hijaab was revealed, so the women used to wear the Hijaab in the presence of men, and ‘Aa’ishah said in the long Hadeeth in the story of Ifk [when she was falsely accused of adultery]: "He [i.e. Safwaan ibn Al-Mu'attal] knew me when he saw me, and he used to see me before the Hijaab was imposed on me…"
Moreover, ‘Aa’ishah narrated that the wives of the Prophet used to go out by night to open fields to relieve themselves (to answer the call of nature) in the outskirts of Medeenah (near al-Baqee' graveyard) and 'Umar ibn al-Khattaab used to say to the Prophet : "'Ask your wives to observe the Hijaab’, but the Prophet did not do that. So one night Sawdah bint Zam`ah, the wife of the Prophet went out at `Ishaa' time and she was a tall lady. 'Umar called her saying: 'I have recognized you, O Sawdah.' He did this with the hope that the verses pertaining to the Hijaab would be revealed. 'Aa'ishah said: 'Allah, the Exalted and Glorious, then revealed the verses pertaining to the Hijaab.'" [Al-Bukhaari and Muslim]
For more benefit on the view of some scholars regarding Niqaab, please refer to Fatwa 372655.
Allah knows best.