I am not very familiar with music in general, and I lack the vocabulary to express some commonalities (that I might be imagining anyway). Additionally, what I heard seems to be there is in very derivative music, so in authentic styles they might not exist.
But, listening to some contemporary Arab jazz, gypsy jazz by Django Reinhardt, in Squirrel Nut Zippers (although, that might be gypsy jazz again, rather than klezmer), and some folk, and even contemporary turbo-folk, music with South Slavs, there does seem to be something in common. I'd say it's especially pronounced in violin.
Some examples:
Hijaz - Leaving Adana here from around 6:30, but on Chemsi album in general. (this was the best I could find to easily link)
Squirrel nut zippers - Ghost of Stephen Foster and other stuff.
A lot by Django, but I'll link just Minor Swing
And I don't know what to link for South Slav examples. But again, it might be more of a Roma music, because I've heard (or imagined) most similarities in some "kafane" (don't know if it can be translated, literary coffee house but functioning more for night time entertainment and lots of alcohol) with live Roma bands playing. Still, from there to folk is quite a clear influence line.
I'm guessing either Roma or Ashkenazi might have carried some influences, especially to Eastern Europe, if Middle East or contemporary Palestine is the origin. It there something to it, and if anyone knows, how far back could the connections reach?
I cannot answer the historical aspect of the question, but I can give you the musical terminology: what you're hearing is the Phrygian dominant scale. Hope this helps you narrow the search.