Would Celeborn be permanently separated from Galadriel?

Celeborn did eventually sail west, but it was some time before he did so

Tolkien wrote two drafts of an epilogue that he originally intended to place at the end of The Lord of the Rings, to resolve some of the loose ends. The epilogue is set seventeen years after the end of the book and uses the framing device of Sam talking to his children. Both versions have been published in Sauron Defeated.

Sam reveals that seventeen years after Galadriel left, Celeborn is still hanging around in Lórien, but that he is able to leave and will whenever his time to do so comes.

'Still I think it was very sad when Master Elrond left Rivendell and the Lady left Lórien,' said Elanor. 'What happened to Celeborn? Is he very sad?'
'I expect so, dear. Elves are sad; and that's what makes them so beautiful, and why we can't see much of them. He lives in his own land as he always has done,' said Sam. 'Lórien is his land, and he loves trees.'
'No one else in the world hasn't got a Mallorn like we have, have they?' said Merry. 'Only us and Lord Celeborn.'
'So I believe,' said Sam. Secretly it was one of the greatest prides of his life. 'Well, Celeborn lives among the Trees, and he is happy in his Elvish way, I don't doubt. They can afford to wait, Elves can. His time is not come yet. The Lady came to his land and now she is gone; and he has the land still. When he tires of it he can leave it.
_{The History of Middle-earth volume IX - Sauron Defeated - "The Epilogue" - first version}

'Tell me,' she said, as they sat close together with the soft golden light on their faces, 'tell me about Lórien. Does my flower grow there still, Sam-dad?'
'Well dear, Celeborn still lives there among his trees and his Elves, and there I don't doubt your flower grows still. Though now I have got you to look at, I don't hanker after it so much.' ...

Elanor was silent for some time before she spoke again. I did not understand at first what Celeborn meant when he said goodbye to the King,' she said. 'But I think I do now. He knew that Lady Arwen would stay, but that Galadriel would leave him. ...

They [elves] are not so troubled about time. And so I think Celeborn is still happy among his trees, in an Elvish way. His time hasn't come, and he isn't tired of his land yet. When he is tired he can go.' _{The History of Middle-earth volume IX - Sauron Defeated - "The Epilogue" - second version}

It should be noted though that this version of events is not fully compatible with the final version of the book. In the second edition of The Lord of the Rings Tolkien added two statements that say that after Galadriel left Celeborn moved to Rivendell, and then eventually that he departed Middle-earth sometime afterwards.

In the North also there had been war and evil. The realm of Thranduil was invaded,... but in the end Thranduil had the victory. And on the day of the New Year of the Elves, Celeborn and Thranduil met in the midst of the forest; and they renamed Mirkwood Eryn Lasgalen, The Wood of Greenleaves. Thranduil took all the northern region as far as the mountains that rise in the forest for his realm; and Celeborn took all the southern wood below the Narrows, and named it East Lórien; all the wide forest between was given to the Beornings and the Woodmen. But after the passing of Galadriel in a few years Celeborn grew weary of his realm and went to Imladris to dwell with the sons of Elrond. In the Greenwood the Silvan Elves remained untroubled, but in Lórien there lingered sadly only a few of its former people, and there was no longer light or song in Caras Galadhon.
_{The Lord of the Rings - Appendix B}

It is probable that Meriadoc obtained assistance and information from Rivendell, which he visited more than once. There, though Elrond had departed, his sons long remained, together with some of the High-elven folk. It is said that Celeborn went to dwell there after the departure of Galadriel; but there is no record of the day when at last he sought the Grey Havens, and with him went the last living memory of the Elder Days in Middle-earth.
_{The Lord of the Rings - Prologue - "Note on Shire Records"}

Hammond and Scull refer to an unpublished letter of Tolkien's where he also confirms that this parting was only temporary.

These comments imply that Celeborn could have left Middle-earth with Galadriel if he had wished, and Tolkien’s replies to queries from readers seem to confirm this. In his unpublished letter to Eileen Elgar, begun 22 September 1963, he comments that Celeborn and Galadriel were of different kin: Celeborn was of that branch of the Elves that, in the First Age, was so in love with Middle-earth that they had refused the call of the Valar to go to Valinor; he had never seen the Blessed Realm. Now he remained until he had seen the coming of the Dominion of Men. But to an immortal Elf, for whom time was not as it is to mortals, the period in which he was parted from Galadriel would seem brief.
_{The Lord of the Rings A Readers Companion - Book VI Chapter 6 - "Many Partings"}