Messages are not included in your iCloud backup as they automatically upload to iCloud. After you restore to a backup you need to stay connected to iCloud and your messages will download.
From this Apple Discussion:
When you use Messages in iCloud, your text messages automatically upload to iCloud. They aren’t included in your backup. After you restore your device from iCloud Backup, stay connected to Wi-Fi so that your text messages can begin to download.
From this Apple Discussion:
When you delete a message, photo, or conversation on one device, it’s removed from all of your devices. And since all of your attachments are stored in iCloud, you can save space on your device.
If the messages are deleted it is not possible to recover them:
Correct, my assumption (incorrect it seems) was that because the message history is now stored in iCloud, a message could be deleted from my device, but the message history could be accessed/reloaded again later. It seems that's not the case.