Since both Windows Update and Microsoft Store have been affected, and the problem has reportedly persisted for around 3 years, the most likely cause is corruption within Windows system files or servicing components rather than a Store-specific problem.
While there are individual troubleshooting steps that can be attempted, the length of time this issue has existed suggests the operating system may be significantly outdated and that the corruption could be extensive.
I recommend performing an in-place upgrade (repair install) using the latest Windows installation media. This process reinstalls Windows while preserving your personal files, applications, and settings. It can repair corrupted system files, rebuild Windows components, restore Windows Update functionality, and repair Microsoft Store components at the same time.
Disclaimer: Let’s try performing an in-place install or in-place upgrade which will refresh your Windows files and operating system without removing files or applications. That being said, we always recommend that if you have important data, you should back it up before making large system changes. If you want to back up your data first, please do so. Once you are done backing up, you can follow the steps in the following guides: How to run In-place upgrade in Windows 11 - Microsoft Community
After done so, your system will get 25H2 directly without needing of installing several patches.
If you have further information, please feel free to let me know.