Here in the actual world A we have a ship, let us name it the good ship Theseus, made of 1000 planks. Our first intuition X is that the same ship could have been made of 999 of these planks plus a replacement for plank #473. In possible-worlds terms that means there is another world B where the same good ship Theseus exists with all but one plank the same as in our world A, and only plank #473 different. But then in world B one has a good ship Theseus made of 1000 planks, and by the same sort of intuition, there must another world C where the same good ship Theseus exists with all but one plank the same as in the world B, but with plank #692 different. That means for us back in world A there is another world C where the good ship Theseus exists with all but two planks the same as in our world A, but with planks #473 and #692 different, so one could have two planks different and still have the same ship. The same sort of considerations can then be used to argue that one could have three planks different, or four, or five, or all 1000. But that is contrary to our other intuition Y [a ship made of a thousand different planks would have been a different ship].From John P. Burgess, "Modal Logic, In the Modal Sense of Modality" pp. 40-1.
The modal paradox resembles well-known paradoxes of vagueness, such as the heap and the bald one, for which proposed solutions are a dime a dozen — except that here what seems to be vague is the relation of identity. And the idea that ‘is the very same thing as’ could be vague is for many a far more troubling idea than the idea that ‘heap’ or “bald’ is vague. Indeed, according to many, it is an outright incoherent idea.
In the fourth line Burgess says "by the same sort of intuition," which is a relatively weak sort of thing to say, and so it might be where the paradoxical reasoning started to go wrong. Our original intuition X was that in the actual world A, Theseus could have had one plank different and still have been the same ship. We know, equally intuitively, that X coheres perfectly well (somehow) with the intuition, Y, that in the actual world A, Theseus could not have a thousand planks different and remain the same ship. Whereas the ship in B is not exactly the same as the ship in A. And the meanings of all our words are rooted in A. The further we get from A, the more vague we might expect our meanings to become.
In the first line of the second paragraph Burgess observes that proposed solutions to the paradoxes of vagueness are "a dime a dozen" and that means, I think, that anything I might say is bound to pointlessness; but, onward and upwards. And it is certainly the case that "the very same thing" often equivocates, as in the case of the famous clay statue: if that thing is squashed then, while it is the same lump of clay, it is no longer a statue at all. So let us look at a very different formulation of the ship paradox, one that does not involve modality at all. The following is by Ryan Wasserman, "Material Constitution", §1:
[...] the story of the famous ship of Theseus, which was displayed in Athens for many centuries. Over time, the ship’s planks wore down and were gradually replaced. [...] Suppose that a custodian collects the original planks as they are removed from the ship and later puts them back together in the original arrangement. In this version of the story, we are left with two seafaring vessels, one on display in Athens and one in the possession of the custodian. But where is the famous Ship of Theseus? Some will say that the ship is with the museum, since ships can survive the complete replacement of parts, provided that the change is sufficiently gradual. Others will say that the ship is with the custodian, since ships can survive being disassembled and reassembled. Both answers seems right, but this leads to the surprising conclusion that, at the end of the story, the ship of Theseus is in two places at once. More generally, the argument suggests that it is possible for one material object to exist in two places at the same time. We get an equally implausible result by working backwards: There are clearly two ships at the end of the story. Each of those ships was also around at the beginning of the story, for the reasons just given. So, at the beginning of the story, there were actually two ships of Theseus occupying the same place at the same time, one of which would go on to the museum and one of which would enter into the care of the custodian.For myself, I do not think that the ship in the museum was the famous Ship of Theseus, I think that what was left of that ship is now the custodian's ship. But I concede that it could be that the museum ship is legally the ship of Theseus. It would then follow that the custodian's ship was not, for legal purposes, the ship of Theseus. So I think that there are at least two senses of "ship of Theseus" in play. What we can say about those senses is another matter. Our language is inextricably rooted in the usual events of the actual world. But it could be scientific to know that there are those two senses even before our theories of such senses have become a dime a dozen. And we might find clues as to what we should be saying from related puzzles.
There are many intuitive puzzles about identity. For just one example, suppose that the world that you are in splits into two worlds, so that you are in one while an identical person is in the other. You are the same person as the original you, of course, but so is the person in the other world. So, that other person is the very same person as the original you, who is the very same person as you, and yet that other person is not the very same person as you. So, either personal identity is not always a transitive relation, or else this scenario is impossible. And while the latter is certainly plausible, it seems to me to be the wrong sort of conclusion to draw from this scenario. Knowing whether it is the wrong sort of conclusion to draw or not may well be a prerequisite for getting anywhere with such puzzles as the modal paradox, because intuitions for "is the very same thing as" not ever being at all vague seem to be very similar to intuitions that it must always be transitive.