"Open the app once and its actions come back" is not a coincidence, and it is the most useful thing in your post. It tells you which half of the system is broken.
App Shortcuts are declared by the app, not built by the system. The app ships a list of actions, and the system has to have that list registered before it can offer them in search. Launching the app is what causes it to register. So what you are describing is a device that lost the registry and is rebuilding it one app at a time as you happen to open things.
That rules out the two explanations people usually reach for first. It is not that the actions were removed from the app, because they come back untouched. It is not the per-app search switches either, because those would not be repaired by launching.
The practical consequence is unglamorous: the apps you use will fix themselves within a week or two of ordinary use, and the ones you rarely open will stay empty until you open them. If there are three you actually want back today, open those three and stop worrying about the rest.