Here’s my take on this.
Recovering deleted messages on Android can be a tricky process, as there isn’t a universal, user-accessible “recycling bin” for SMS.
On one hand, your first instinct to check cloud backups was the correct one. That’s the most reliable method, but as you’ve seen, it’s only as good as your last sync. Some messaging apps now have a temporary trash folder, so it’s always worth double-checking there first.
On the other hand, you have third-party data recovery software. These tools scan your phone’s storage for data that has been marked for deletion but not yet overwritten. The fact you haven’t used the phone much increases your chances. The main drawback is that success is never guaranteed, and many “free” tools only let you scan, requiring payment for the actual recovery.