You need to set the ClientObjectX.Client reference to null in addition to removing it from the collection. Removing it from the collection does not make it an orphan so it will not be deleted when the session is flushed.
var objectX = client.ListClientObjectX[0];
client.ListClientObjectX.Remove(objectX);
objectX.Client = null;
It might be a better idea to break the operation up into two transactions; one to delete and another to add an object with the same unique combination. I think you are asking for trouble if you frequently add and remove objects with the same unique combination in a single operation.