You'd basically need a long and corrosive war. It's not so much that the Med is thought of as belonging to Europe as that no state with a strong government will permit that kind of thing on its doorstep. It's why the (northern) Caribbean ran out of pirates, too. So to get there, France, Italy, Spain, Turkey, Portugal, Egypt and Greece need to be destroyed as functioning states (North Africa itself is less of a problem - I suspect that most of it is destined for anarchy once the colonising powers are thus gone).
I like the idea of US-backed crime organisations to fight the Communists, but I think you still need a big POD to make it go to that extent. Maybe if the Soviets get control of Germany, France, Italy and Greece and the USA prevails on Turkey, Egypt, Syria, Spain and Portugal to tolerate piracy, drug-running and coastal raiding to the point that by the 1960s, organised crime pervades their governments?