Since buying Halo MCC on Pc on steam, I’ve had the same message claiming I am not connected to Xbox Live when trying to access any online matchmaking, I have reached out to the Xbox live customer support line as well as submitted a ticket for Halo support to no avail. I have had this problem since the release of the game on December 3rd. I’ve tried uninstalling the game several times and went as far as to attempt accessing multiplayer through different Xbox live accounts and still no solve. I hope someone might have the same issue so I don’t have to play just custom and campaign.
Do you use a VPN? That will block access to multiple Microsoft programs.
I had the same problem