Guest access stopped working

We have enabled guest access in our tenant and it's been functioning well for the past month. We've added external guests with multiple domains, including 3 with microsoft.com account. When we try to add a new guest (also with microsoft.com domain), we get the "no results found" message. This has been ongoing since September 27. I double-checked that everything is the same for guest access in groups, teams, SP and AAD.

Anyone else seeing this behavior?  Thanks