So, it looks like we know the Rahshid's age. 706 give or take a couple years. Firstly, I'm assuming he is also a starborn, so he is Harry's age plus some multiple of 666 years. Call Harry's bday around 1975, the previous starborns were round about CE 1330, CE 670, CE 1. Even wizards usually don't live 1000+ years so 1330 is most likely.
But if something hinky went on with time/life, I still think 670 is the earliest possible. Rashid seems to be an Islamic name, and assuming it is his original name that would put him sometime after 630-ish. Plus if you further back you run into problems like being pre-swords of the cross, possibly knowing the Merlin and the original Warden. Just starts feeling wrong.
Also, it's interesting to know more about Listens-to-Winds teacher.