Messages in iCloud Won’t Delete from macOS
As of macOS 10.13.5 High Sierra, it appears you need to disable Save history when conversations are closed for message deletion to function as advertised over iCloud.

To do this, open Messages, then from the menu bar navigate to Messages → Preferences… → General. Uncheck this box:



It’s unclear whether this is the expected behavior, but it sure looks like a bug.