Updated first post:
I'm also sticking to using "Region" instead of "Province". Makes little difference I think.
I could use more help with places like Syria, Egypt, Anatolia, the 'steppe', India etc.
Region names I added in are:
Oman, Armenia, Yemen, Sistan, Kerman, Jibal, Fars, West Khorasan, East Khorasan, Sindh, Gujarat, Iraq, Hijaz, Arran, Azerbaijan, Tabaristan, Gurganj, Khwarazm, Transoxania.
A HUGE thanks to Nnnm and the following map which pretty much gave me all I needed for the eastern regions, except for India and Afghanistan (most of afghanistan being in "khorasan" or Ghazna province though).