Mac App Store not reliably showing available app updates

A VPN will block access to Apple Servers for automatic update checks from the OS. Uninstall the VPN and compare your results. Turning off makes no difference as they still have processes running in the background.

If after removing the VPN, you still experience the same thing, then post the free EtreCheck report with the Additional Text option when posting. It will identify other network blocking processes that are contributing to the problem you see and the report contains no personal information. The problem you are having is unique to your setup and will remain until that third party process is removed from your Extensions/Launch folders.

How to use the Add Text Feature When Post… - Apple Community

Yep, you have identified to 2 most likely ones that interfere with network connections. After uninstalling, make sure you check the EtreCheck report again to verify they have all been removed from the System Folders. Dragging to the trash will not work and sometimes even the uninstaller fails to remove all files.

Also make sure com.nordvpn.macos.helper.plist gets removed from your LaunchDaemons folder as that one in particular is marked as Not Signed. It is never a good idea to have files installed that are Not Signed, as many of those are found on those websites that act as an App Store for downloading apps, but the files that are installed may have been altered. That is not specific to the issue you are having, just a general recommendation to avoid Malware.

You can see that the Hosts file has likely been modified by LittleSnitch as /etc/hosts - Count: 1 in the report, so hopefully that will also return to the default after uninstalling. The Hosts file is responsible for routing internet connections.

I am not familiar with PearCleaner, so I don't have any specific info to provide on its use. For the most part Cleaners are not recommended as the usual one is CleanMyMac and that has given all of them a bad name with the problems it has caused on Macs throughout the years and also seen extensively here just by searching for CleanMyMac using the Search tab on the top of the page.

Doing this is just an effort to resolve the problem without performing a Factory Reset. You can always reinstall after testing without any data loss. It has not been seen here where there has been a problem with Mac App Store updates in this or previous Mac OS versions, so it would seem like something specific is going on with your setup and the testing by uninstalling is much easier than the clean install of a Factory Reset.