I’m going to nominate Accept, either Restless and Wild or Balls to the Wall. An under-appreciated band, IMHO.
Well, Zep have a few Egyptian melodies which are similar to middle eastern 
( get hold of No Quater - Plant and Page, Unleaded dvd ). I think Extreme had some middle eastern styled melodies as well.