Actually given the correct set of search parameter permissions Spotlight
might be able to dig that out. First you would have to use Spotlight via Finder (⌘F) on the desktop. Then enable searching for system files, invisible files, the database path, searching for contents,
etc.. I have no idea what the
magic set of options might be , there are over 100 different parameters but the majority of these would not be appropriate.
There are third party search tools such as
Find Any File or
MagicianFile that use a brute force (open read and search every file one at a time) that might work as well. Remember too that when you get into Time Machine, file structures and linkages can get pretty baroque, so extracting the data once you find it can become a challenge.
iCloud gets involved in all of this as the medium for keeping all of you devices synched, but once a message is deleted on any one of your devices it is deleted from iCloud and all of your other devices. I have no idea what type of backup Apple uses with iCloud, but to go back in time there would most likely require Apple to turn extensive and extremely expensive handsprings.