How about an Arabic style font? I'm not sure it's the way to go and it might prove too hard to read, but it is another option. I realise the text is probably the least fitting with the theme, but we have to consider playability here. I think any territory should be easy to identify quickly, so that's key. I'll see what I can come up with though.
As for the edges, I was originally doing exactly that... having the border that seems to be on so many old maps. I really needed the extra map space though and wanted the territories to be as big as possilbe. If you look at the current Middle East map and Mr. K's version, you'll see I've zoomed in quite a bit as it is. I will look into this though, even if it is just to roughen them up to add that aged look.
