What is the difference between "a desert island" and "a deserted island"? Are they synonymous?
I think people are being misled by overly literal interpretations. Let's first note this definition from Oxford Dictionaries (it's also the one automatically shown by Googling define desert island)...
desert island - a remote tropical island, typically an uninhabited one
"Carwyn seemed like a castaway on a desert island"
I would say that word "typically" is crucial, in that it implies a desert island might not in fact be uninhabited. Particularly since the usage example implies at least one inhabitant (the castaway lives there, even if he hopes his residence will be temporary).
More importantly, I can find any number of online definitions for desert island (that's 5 just there). To all intents and purposes, no dictionaries explicitly define deserted island - if you want to know what that means, you have to look up each word separately and work it out yourself.
Actually, that's not strictly true. If you search for define "deserted island" Google appears to show a definition for those exact words, but in fact it's just redirecting to the desert island definition. Wkipedia does something similar, in that the page http://en.wikipedia.org/wiki/Deserted_island goes to the same page as http://en.wikipedia.org/wiki/Desert_island.
I hope that's enough to show desert island is a well-known collocation with numerous specific connotations to most Anglophones (notably including Robinson Crusoe, Desert Island Discs, and humorous postcards). Whereas deserted island is just two words that might occur consecutively.
In short, whether there's any etymological justification for it or not, most Anglophones understand desert island as tropical, sandy-beached, [probably] without permanent inhabitants, etc., etc. They certainly wouldn't use that collocation in respect of uninhabited islands of Scotland, for example (which they might well be prepared to call deserted islands).
TL;DR: desert island evokes arid, sandy, desert-like, deserted evokes uninhabited, abandoned.
Dictionaries can only take you so far. In this case, established cultural associations are crucial.
They are often used as if they were synonymous… But, "a desert island" is "an island which has never been inhabited, which is and has always been uninhabited", whereas "a deserted island" should mean "an island which once was inhabited but whose inhabitants left for one reason or another, whose inhabitants deserted it".
Although I am sure that this should, this normative attitude towards languages, is definitely not everybody's cup of tea!
This reminds me of a game show I once saw on (French) TV: the people on set were given a phrase like 'not to beat about the bush' and given four different meanings the phrase might have.
The presenters had asked a hundred people in the street to choose between the different meanings. To win the game, the people on set did not have to give the correct meaning of the phrase, but the meaning which had been chosen by most people.
At first this sounded preposterous to me… but then it dawned on me that this is exactly the way languages work in the long run: a mistake made by a majority of people ends up not being one!
An example: in French, the morello cherry — a variety of very dark sour cherry — is l'agriotte from aigre, meaning 'sour' ('eager' belongs to the same word family as aigre). A lot of people misdivided this and ended up with la griotte… which is the correct form today! This is parallel to Shakespeare's humorous nuncle used by the Fool to address King Lear, a misdivision of an uncle, like so many innocent ones coming from the mouths of children.
Similarly, when enough people have used Huckleberry Finn's nonnamous instead of anonymous, when Greek is Greek to enough of us, and when humorous or mistaken has become plain, nonnamous might become correct!
I think it is one of those phrases which has gotten misused with time. Deserted island became desert island because people left off the "ed". There us no basis of comparison for an island with a desert because the word desert has an explicit meaning which is unrelated to an island unless the topography is like that of a desert and the fact that it is surrounded by water dismisses some if that slight similarity even.