I would not make that assumption. You have adequate reason to conclude your earlier suspicion is correct:
Wondering if "Clean My Mac" has "cleaned" away necessary files (or system files) affecting Mail app?
The answer to that is almost certainly yes — specifically, the "cleaning" app removed one or more files essential for that User Account's Mail message management database, rendering it corrupt and unusable.
Although it is not possible for such things to corrupt or otherwise alter macOS itself, of which the Mail app is an integral component, anything in the user space — including files and operating system components essential for the proper functioning of the Mac — is fair game for them to remove, rendering that User Account corrupt in ways that are not practicable to correct or restore.
There are measures short of erasing the Mac but they are time-consuming and (in my opinion) not worth the effort. You can, for example, completely remove all Mail-related files in that User Account, methodically add each email account all over again, but given the unfettered ability for non-Apple "cleaning" products to affect other, completely unrelated apps it will always remain a concern until the Mac is completely erased and rebuilt from the ground up.
But now I understand that Apple doesn't actually recommend it even though I got it from the Apple store, I won't use it again.
To be clear, Apple makes no recommendations for or against any software, no matter where it's from. The fact it may be in the App Store has no bearing on that. Arguably, most apps in the App Store are garbage products no one needs. But everything in the App Store makes money for the developer as well as for Apple, so that will never change. If their installation and use results in a Mac working poorly, sometimes the user will conclude the Mac is just too old and worn out and needs replacing, so they go out and buy a new Mac whether it's justified or not. Apple certainly won't mind.