How many devices are you logged into Messages in iCloud? Do any of those devices sit around unused for any length of time? For example an iPad laying around collecting dust, or a Mac you only once a week, maybe less?
SMS are difficult to sync because they are difficult for Apple to track. Since an SMS can be sent without using the internet via cell providers SMS centers you and all your devices can have and already modified the data prior to iCloud even knowing it exist. Combined that with SMS failed to deliver errors but the SMS was actually delivered its a miracle it even works at all.
What I find helped when things got really bad for me is to delete all your messages using your iPhone. Make sure all your devices have a good internet connection and wait 15 minutes once your done with the iPhone. Then check your other devices to see if there are messages that remain, if so delete them. Once you are done turn off iMessage on each device one at a time for 1-2 minutes then turn it back on. Make sure no more messages pop up. Important to give time between all the steps so everything is sync'd.
As far as the Apple Watch goes its not a Messages in iCloud device like the iPhone, Mac, iPad or iPod Touch. There are situations where deleting a message from an iPhone will delete it from the watch however that isn't always the case. The Apple Watch is very limited resources so its designed to do its own thing.
The Apple Watch only retains 30 days of messages, from individual conversations to total conversations there is only 30 days there. Which is a design based around not deleting anything and allowing the Watch to purge old messages after 30 days.
Plus the media received on the Apple Watch is transcoded using very lossy compression that transcodes from h265 to h264 and HEIF to JPEG. Resolutions are reduced and bitrates are reduced at the expense of quality. This is all to minimize the amount of storage and processor cycles while having a minimal impact on the media when viewed on the watch.
But basically there is nothing to sync there its two different sets of data that just contain very similar information. But iMessages can be deleted via another device and it delete off the Apple Watch, not vice versa though.
