Using SnapshotStateList with LazyColumn: adding new items causes IllegalArgumentException key was already used

Question

I have a basic SnapshotStateList that I add and remove items from. It's stored in a MutableStateFlow along with the rest of the UI state for this screen, and exposed as a StateFlow to the composables, on my ViewModel, because I sometimes want to be able to swap the entire list out for a completely different one, but that will only happen when the rest of the UI state needs to be swapped out as well. Here's what that looks like (in miniature):

date class SomeUiState(
    val channelId: String? = null
    // ... other UI state ...
    val messages: SnapshotStateList<Message> = mutableStateListOf()
)

@HiltViewModel
class SomeViewModel @Inject constructor(
    // Messages repository exposes messages for each channel as MutableStateFlows, and handles adding, removing, and updating messages as necessary inside itself.
    private val messagesRepository: MessagesRepository
) : ViewModel() {
    private val _uiState = MutableStateFlow(ServerChannelUiState())
    val uiState: StateFlow<ServerChannelUiState> = _uiState.asStateFlow()

    // ...

    init {
        viewModelScope.launch {
            currentChannelStateFlow.collectLatest { channelId: String? ->
                _uiState.update {
                    it.copy(
                        channelId = channelId,
                        messages = messagesRepository.getMessagesForChannel(channelId)
                    )
                }
            }
        }
    }
}

This SnapshotStateList is then consumed by a LazyColumn, like so:

val uiState by channelViewModel.uiState.collectAsState()
LazyColumn {
    itemsIndexed(
        uiState.messages,
        key = { _, it -> "${it.messageId}${it.timestamp}" },
    ) { index, message ->
        Message(message)
    }
}

About 90% of the time, this works fine, even across many adds, deletes, adds again, updates, etc. But 10% of the time, adding a new message triggers an IllegalArgumentException "key is already being used." I assumed this was because the server was reusing message IDs from previously deleted messages for new messages, so I made the message timestamp part of the key, since for a new message to reuse the ID of an older deleted message, it must obviously be created after the deleted message, just by its very nature. I even made the timestamp include the millisecond the message was created, so collisions would be extremely difficult. This changed nothing. I kept getting the exception. So I changed tack, and had my program log every, single, one of the message IDs and timestamps it ever put in its messages list. By doing this, when adding a new message produced the "key was already used" error, I was able to confirm that the key LazyColumn was claiming had already been used... had in fact not already been used, since I had a list of all previously used keys to check it against.

So LazyColumn is very clearly marking brand new, unique keys as duplicates of themselves when they're added into the list. What is causing this? Is there any way around this? I don't want to have to switch to SharedFlow<List<>> or something because that would mean a complete rerender of LazyColumn every time any change is made, which would be catastrophic for the performance of an often-used messaging app.