When you restore a backup with those messages in it, the next iCloud for Messages sync will just erase them again, just like you saw with the offline device. I don't know of any way to undo/remove the delete operations for those messages in the iCloud for Messages sync history.
If you wanted to experiment, we could see if there is a way to tweak the messages in (a copy of) the backup to reintroduce those messages as if they were new/different messages and not the ones iCloud for Messages has recorded as deleted. That is if you have patience, a spare device to restore the adjusted backup to, and the phone number and date range of messages you want to try to put back ;)
You could also choose extract the messages out of the iOS backups you have with a third party app (the one I am a developer for is Decipher TextMessage, there's also ones like iMazing and iExplorer). That won't help you re-merge the content onto your iPhone/iCloud for Messages database, but it will give you access to the information in them if that is what is important.
