FYI: We worked with Microsoft over night, and we found the culprit of the issue.
TL;DR: The site-server computer-object was missing the necessary privileges to publish site-data to ADDS.
The error was somewhat specific to our environment, as it tied together with a server migration we performed on our ConfigMgr server some 3 months ago (2012r2 -> 2019). We installed a new server and renamed the old server to "sccmserver-old" while the new server got the old SCCM Server name "sccmserver". However, it seems a migration step that was actually in our migration plan was missed. Specifically we needed to make sure the new computer object was added to the relevant AD Groups that gave it the permissions to publish site data to ADDS.
Apparently this also had a delayed fuse, as the impact of the error we are seeing here where no agents is able to communicate with MPS, only triggered after a routine upgrade of ConfigMgr to 2107.
This was otherwise also correlated by the Microsoft engineer from the following logs:
"From locationservice.log
Retrieved lookup MP(s) from AD LocationServices 9/3/2021 1:44:35 AM 3684 (0x0E64)
Raising event:
instance of CCM_CcmHttp_Status
{
ClientID = "<Removed>";
DateTime = "20210902234435.700000+000";
HostName = "<Removed>";
HRESULT = "0x00000000";
ProcessID = 2744;
StatusCode = 0;
ThreadID = 3684;
};
LocationServices 9/3/2021 1:44:35 AM 3684 (0x0E64)
Failed verify the signature for issuing root cert list blob .... </Cert></Certs></SMSIssuingCerts>' with error '0x80090006' LocationServices 9/3/2021 1:44:35 AM 3684 (0x0E64)"