С другой стороны невозможность удалять “сообщение удалено” создает лишнюю нагрузку на сервер, клиента и провайдера и почему оно сделано так (а не как в WeChat или Signal) для меня загадка.

И для меня тоже. Имхо должно быть как минимум два варианта: просто удалить и удалить бесследно.

У меня нет проблемы с “сообщение было удалено”, но у меня есть проблема с тем, что это нельзя удалить)

А в наших местных реалиях (да и в ваших тоже, просто ты, видимо, не сталкивался) это создает порой очень серьезные и реальные проблемы при попадании девайса в чужие недобрые руки. И тогда у них сразу возникает причина и желание вывернуть тебя наизнанку, даже если ты на первый взглял белый и пушистый.