I don’t have any experience with data recovery services, but before paying out, I would talk to Apple. Or better yet, first try to use its tools for recovering deleted iCloud files. I’m not hopeful that will work, because it specifies “deleted” files. The missing files weren’t expressly deleted by you, but seem to have been removed by the system because you deleted the app. So, I don’t know if Apple considers those files as “deleted”. But it’s worth a try!
If that fails, I would call Apple support to see if they have a way to restore these app-associated files.
This is not expected behavior. Throwing out an app should not delete the files that are explicitly stored in a folder that is visible to the user and appears to be just like any other folder. In fact, iOS explicitly asks you if you want to keep the data when you delete an app. Of course, that’s because the user doesn’t have explicit access to the filesystem in iOS. But if the Mac is behaving similarly, you should have been warned.
Regarding Time Machine, it’s concerning that it shows no backups. Of course, a huge problem with Time Machine is how it interacts with iCloud data.
Apple explicitly says that “Time Machine excludes system files and apps installed during macOS installation”. That’s it. Perhaps because of iCloud Drive’s legacy behavior on the Mac, these app-specific folders are not backed up because they’re considered part of the “system files”? If so, that’s a huge oversight.
Or, if you used the “optimize” function, perhaps those files were never present on the Mac being backed up by Time Machine. If they never were downloaded, they can’t be backed up. Again, that’s a huge oversight by Apple because this is never explicitly stated anywhere and users aren’t given a warning that the files that appear to be on the computer aren’t actually there. (I know, you can look at the icons carefully, but most of my clients are clueless about this.)
More importantly, if these missing files were never present on the Mac, then no data recovery service is going to work.
All of the Time Machine marketing emphasizes how it backs up your data, when in fact there are holes in that system. And worse, those holes can lead to data loss.
I’m really sorry you’re facing this. Hold Apple’s feet to the fire about your loss of data. They might have to dig into their servers to recover your missing files, but they should be made to feel the pain so they fix these holes. Good luck!