From everything I have read on the Apple forums, this is a very common problem among most Apple Watch owners. Since this problem has been present for years now, I would assume that Apple is aware of it, but I am not sure why it has not been addressed.
I did learn that the Apple Watch does not back itself up to iCloud. All watch backups are stored on your iPhone, then they are included in your phone's iCloud backups. So I am not sure if the Apple Watch ever connects to iCloud directly. This is why you do not have iCloud backup / sync settings on your watch.
The only setting for iMessages that you specifically have on your watch is to mirror iPhone or set it to custom. So at this time, it looks like your Apple Watch is still tethered to your iPhone in many ways. Time will only tell if and how much this might change with the next major release of watch OS.
I do agree and think that the deletion of messages should have reflected on both devices back from the start. And since they don't, should be a something that is at the top of the priority list to get working properly.