Smart Mailboxes Don't Save (Disappear)!!

Give this a try: boot into Safe Mode according to How to use safe mode on your Mac and test to see if the problem persists. Reboot normally and test again.

NOTE 1: Safe Mode boot can take up to 3 - 5 minutes as it's doing the following; 

• Verifies your startup disk and attempts to repair directory issues, if needed

• Loads only required kernel extensions (prevents 3rd party kernel/extensions from loading)

• Prevents Startup Items and Login Items from opening automatically

• Disables user-installed fonts 

• Deletes font caches, kernel cache, and other system cache files

NOTE 2: if you have a wireless keyboard with rechargeable batteries connect it with its charging cable before booting into Safe Mode. This makes it act as a wired keyboard as will insure a successful boot into Safe Mode.

Have you installed and run any "cleaning", "optimizing", "speed-up", anti-virus or VPN apps on your Mac?

I am sorry but this may well be self-inflicted… cleanmymac is probably causing it. This thing should never ever ever be installed.

Start by completely uninstalling cleanmymac. I thought that was implicit...

First, there is no reason to ever install or run any 3rd party "cleaning", "optimizing", "speed-up", anti-virus, VPN or security apps on your Mac.  This documents describe what you need to know and do in order to protect your Mac: Effective defenses against malware and other threats - Apple Community and Recognize and avoid phishing messages, phony support calls, and other scams - Apple Support.  

There are no known viruses, i.e. self propagating, for Macs.  There are, however, adware and malware which require the user to install although unwittingly most of the time thru sneaky links, etc.   

Anti Virus developers try to group all types as viruses into their ad campaigns of fear.  They do a poor job of the detecting and isolating the adware and malware.  Since there are no viruses these apps use up a lot of system resources searching for what is non-existent and adversely affect system and app performance.

There is one app, Malwarebytes, which was developed by a long time contributor to these forums and a highly respected member of the computer security community, that is designed solely to seek out adware and known malware and remove it.  The free version is more than adequate for most users.  

As you've already been informed CMM is considered to be akin to malware by most of the long time contributors to these forums. Uninstall it according to the developer's instructions. You can check to see if you've removed all of the supporting files by downloading and running the shareware app Find Any File to search for any files with the application's or the developer's name in the file name.  For the CMM software you'd do the following search(es): 

1 - Name contains cleanmymac

2 - Name contains macpaw

Any files that are found can be dragged from the search results window to the Desktop or Trash bin in the Dock for deletion.

FAF can search areas that Spotlight can't like invisible folders, system folders and packages.  

If you get warnings that the file can't be deleted because it is in use or used by another app boot into Safe Mode according to How to use safe mode on your Mac and delete from there.

Note:  if you have a wireless keyboard with rechargeable batteries connect it with its charging cable before booting into Safe Mode.  This makes it act as a wired keyboard as will assure a successful boot into Safe Mode.

Here's some food for thought: unless you're using a true VPN tunnel, such as between you and your employer's, school's or bank's servers, they provide false security from a privacy standpoint.  Read these two articles: Public VPN's are anything but private and Former Malware Distributor Kape Technologies Now Owns ExpressVPN, CyberGhost, Private Internet Access, Zenmate, and a Collection of VPN “Review” Websites. 

Boot into the Recovery volume (boot with the Command + R keys held down  - Intel Macs) or  (How to Boot an M1 Mac into Recovery Mode) and reinstall the system. It won't affect your user data. However, good practice says to be sure to have a full and current backup before attempting any such operation.

iCloud syncing problems can sometimes be fixed by logging out from iCloud and logging in again.

In this case, I am not sure if this will help, because, as far as I can tell, the smart folders do not appear in iCloud Mail. I am not convinced that iCloud is involved in the present problem, but you can try disconnecting, adding a Smart Mailbox and seeing if there is any difference; then connect to iCloud again. Does that make Smart Mailboxes disappear?