Are there any records of the prophet (saw) speaking to an atheist?
No, because all the Arabs were either polytheists, or Christians, or Jews.
Are there even records of people living in that time and place, who were atheists?
Well the Quran mentions the creed of Ad-Dahriyyah and the Arab idolators who embraced their creed, denying Resurrection,
And they say, "There is not but our worldly life; we die and live, and nothing destroys us except time." And they have of that no knowledge; they are only assuming.
Ibn Kathir says:
They say that there is only this life, some people die while others are born to life, without Resurrection or Judgement. This was the creed of Arab idolators who used to deny Resurrection, in addition to, the creed of the atheist philosophers among them who denied the creation and Resurrection. This was also the statement of atheist philosophers who deny the Creator and think that the world will return to its original form once every thirty--six thousand years, when everything will restart its life--cycle again! They claim that this cycle was repeated for infinity, thus contradicting the sound reason and the divine revelation. They said nothing destroys us but time.