The implication is that it's impossible to delete a message from which a sidebar has been created, right?

Yes, that's correct.

Do we make sure to prevent this on both sender/recipient sides for both keyserver-hosted and DM messages?

The UI handles it well - it isn't possible to create a sidebar from a deleted message.

For the DMs, when we receive an operation about creating a sidebar from a deleted message, we should accept it, as it might be a result of a race condition (user A creates a sidebar from a message, and at the same time user B creates a sidebar from this message, and user C receives an operation from A and then from B).

For the thin threads we can consider adding some more validation on the keyserver side. We block creating sidebars from DELETE_MESSAGE but we don't check if e.g. TEXT_MESSAGE that is the source of a sidebar currently being created was deleted. Introducing this check isn't too complicated, but I'm not sure if it is that necessary - the clients should handle this case well because creating a sidebar and then deleting a message from which it was created produces the same result and is a valid scenario.