We must understand that the words "and some say he dwells there still, until the Last Ship sets sail into the West" derive from the Red Book of Westmarch (see Prologue, "Note on the Shire Records"; Appendix A, first paragraphs), and not from the original Red Book, which has not been preserved, but from a copy of it, the first of them being the Thain's Book, copied in F.A. 172. Thus the speculation about Círdan still dwelling in Mithlond cannot be exactly dated to a period before Elessar's and Arwen's death even if Arwen's words might refer to the fact that Círdan had already left Middle-earth.
Arwen also may have referred to her own choice: Elrond left but she remained in Middle-earth, and therefore no ship would take her to the West even if she changed her mind. She had made Lúthien's choice and that was irreversible. "Nay, dear lord," she said, "that choice is long over. There is now no ship that would bear me hence." This is Arwen denying the possibility of returning to the West. But why Elessar would be less informed about the situation in Mithlond, when he suggests that Arwen might return? Would he even speak about sailing to the West if he knew Círdan had departed? That would have been cruel. --Tik 08:12, 29 March 2019 (UTC)
P.S. It seems that Hammond and Scull also have their say about Arwen's words: "It is not clear whether Arwen means that she would not be granted a place on a ship, or that the Havens are Deserted and even Círdan has left Middle-earth (see p. 1039, III: 319-20: 'At the Grey Havens dwelt Círdan the Shipwright, and some say he... '). The latter may be implied by Aragorn's statement that Rivendell is now deserted, and later in the tale Lothlórien is said to be silent." (Reader's Companion, p. 702) --Tik 08:25, 29 March 2019 (UTC)
Didn't the Silmarillion in the end say no records were known to tell when Celeborn left Middle-earth? Well, we do have records up to the death of Eldarion, so I would say the Last Ship left probably thereafter, definitely after the death of Arwen. Faenor 22:14, 14 February 2020 (UTC)