Managing personal Outlook.com account settings, security, and privacy
Microsoft claims that they "removed the ability to connect any other accounts to Outlook.com on May 10, 2021, but accounts connected before May 10, 2021, will continue to sync." They also claim that "Premium customers can add their Google Mail and Calendar accounts as an additional mailbox." I suspect that, in removing this capability, they managed to break the feature itself -- even for premium users.
One problem I was having was that my connected Gmail account was still visible in the sidebar (even though I was getting the OP's same 400 error) and the option to remove the connected account under Settings > Mail > Sync Email was no longer there. After some digging, I found this option has been moved to Settings > Premium > Features > additional mailboxes. From here, I was able to successfully remove the connected Gmail account. However, when I tried to add a new account from scratch, I immediately got the 400 "bad request" error, which means it's not a problem with the connection to Google, but with this Outlook.com feature.
It seems that Microsoft is intending to have an "additional mailboxes" feature for premium users, but it's just broken.