Hi John-Marcum ,
Are you still having issues with uninstalls?
Keep in mind that there is no such thing as a "new Store". The Microsoft Store and its capabilities have been as they've always been. What's new is the integration in Intune with the Microsoft Store to (more or less) enable similar admin controlled app curation and presentation capabilities in Intune that were previously part of the MSfB. In both cases (MSfB and the new Intune integration), the Store itself is still responsible for and actually performs the app installs and uninstalls. There are clearly a couple of additional "layers" involved with the Intune integration (namely the IME and Windows Package Manager), but the core process is actually exactly the same and (as noted) handled by the Store itself. Thus, step one when troubleshooting an issue occurring on multiple systems is to use the Store and then WinGet to manually test the bahvior. You can also reference the log files for each of these components as documented at Troubleshooting the Microsoft Store and Microsoft Intune integration - Microsoft Community Hub.