I can't add much to this Guardian report:
Neanderthal man floated into Europe, say Spanish researchers
Spanish investigators believe they may have found proof that neanderthal [sic] man reached Europe from Africa not just via the Middle East but by sailing, swimming or floating across the Strait of Gibraltar.
Prehistoric remains of hunter-gatherer communities found at a site known as La Cabililla de Benzú, in the Spanish north African enclave of Ceuta, are remarkably similar to those found in southern Spain, investigators said. Stone tools at the site correspond to the middle palaeolithic period, when neanderthal man emerged, and resemble those found across Spain.
The paper is by José Ramos, but I haven't gotten a hold of it yet. The article discusses the fact that Iberia "has older examples of human remains" than other parts of Europe, so I assume the similarities are meant to indicate recurrent contact during the Middle Paleolithic. Hopefully we'll see.