Thousand+ years ago. The al-Mahdi is suppose to be the 12th Imam, coming to the Muslims before the end of the world.
These are some of the characteristics of the awaited one.
http://www.mahdiwatch.org has a lot of information. It is the website where I found the translation of O Ba Ma in Persian = he is with us.
Knew that; I was looking for more depth on the origins, particularly the date of the writings, for which the link helped a bit. As I understand it, Dajjal is Sunni where the 12th Imam is Shiite.
Sunan Abu-Dawud (full name Abu-Dawud Sulaiman bin Al-Aash'ath Al-Azdi as-Sijistani) was born in 202 A.H. and died in 275 A.H.
Given that the Hajj was in 622 AD, that places the recording of these verses somewhere between 844-897 AD. So much for the hunch.