First Part: At what point did Palm trees become considered the inherent part of the fabric of Southern Europe? So much so that they weren't really considered 'imported' anymore? During Arab rule or was it even before that, during Roman/pre-Roman times when Southern Europe/North Africa were culturally closer to each other than maybe they were to Northern Europe?
Second Part: Is it fair to say that palm trees can now, for all practical purposes, be considered native to Southern Europe or do they still have to be imported and planted individually (in other words all the palm trees that we see today in Southern Europe, are they still not able to emerge organically from the soil)?
There are two palm species native to continental Europe: Chamaerops humilis, the European fan palm, which is native to the western Mediterranean (Spain, Portugal, France, Italy, Mediterranean islands including Sicily and the islands to the west of Sicily, and North Africa), and Phoenix theophrasti, the Cretan date palm, which is native to the eastern Mediterranean (Greece, Crete and nearby islands, and Turkey). Both of these European species have been spread more widely as cultivated palms. As both are European natives, they have a very long history along the European Mediterranean coast.
Also with a long history is Phoenix canariensis, the Canary Island date palm, which as the name suggests is native to the Canaries. This was brought to continental Europe through European colonial expansion. Three other species common in Mediterranean Europe were also colonial bringbacks: Butia odorata, the South American jelly palm, from Brazil, Washingtonia robusta, the Mexican fan palm, from Mexico, and Washingtonia filifera, the California fan palm, from California.
The other common species in Mediterranean Europe is much newer, Trachycarpus fortunei, the Chinese windmill palm, which was brought to Europe by the Dutch from Japan in 1830 (and by others from China in the next few decades).
The only wild palm forests in Europe are of the two native species, mostly Chamaerops humilis; the others have not escaped into the wild in significant numbers (and some probably not at all). Some of these species are grown well to the north of the Mediterranean (e.g., Trachycarpus fortunei is grown in England).
The date palm, widely grown in North Africa and the Middle East, was grown in Europe by the Romans, purely as an ornamental plant since Italy is too cold for the date palm to produce fruit. It was again introduced to Europe by the Arabs, cultivation in Spain and Portugal for its fruit. Genetic testing shows that the North African date palm is a hybrid of the Middle Eastern date palm and and the Cretan date palm Phoenix theophrasti, and might have been spread around the Mediterranean coast by the Phoenicians or even earlier by the Minoans. Whether or not this early spread included the European coast of the Mediterranean or just the African coast is something I don't know.