Recover-All-My-Info Said:
"Can you recover messages if you’ve already deleted them and deleted them again from the recently deleted?"
-------
Troubleshooting Deleted Messages:
Search History for iMessage:
As you type in the search bar, existing messages with that content would show up. So, if they do not show up, then they are likely lost.
Troubleshooting Deleted Messages:
What to Consider:
A. Restore from Today's Backup:
Restore your iPhone from a backup of it that contains these messages, and you could recover them.
B. Check Messages App:
If messages was enabled on your iPhone along with your Apple computer, then check and see if the Messages app is enabled on your Mac to see if it exists in it. You'd start up your Mac, not connecting to the Internet, and open the Massages app. Then proceed from there with retrieving it. Important: Be certain you do not connect to the Internet while booting up, as syncing would delete it. So, power off your router to avoid the connection.
Elsewise, if they're gone, they're gone. That's just the way it is :(