When Messages in iCloud is turned on, the messages won’t be included in the iCloud backup. There are also no “Recently Deleted” option for deleted messages. In theory, the deleted messages have gone forever. However, some third-party iPhone recovery software claims to recover deleted messages even without backup as long as they have not been overwritten by new data. No sure whether the tools work.