I have just tried to open a users mailbox using the "open other mailbox" and get the exact same message.
I haven't used that method previously so cant comment if it used to work or not.
Do you need to manually add full access permissions to these new accounts perhaps?
Add-MailboxPermission email@example.com -User firstname.lastname@example.org -AccessRights fullaccess
The users themselves can access their mailbox via either outlook.com or using Outlook on PC's and laptops etc successfully. I will try the above code you have added but generally all the accounts created in the past using this method worked previously.
I did have a database deadlock two weeks ago which was not helping and I ended up clearing out the management agents via a method I found from the UK from the following website ILM 2007 FP1 error with Live@edu - The cookie with domain controller 'GUID' has expired and should be abandonded ILM 2007 FP1 error with Live@edu - The cookie with domain controller 'GUID' has expired and should be abandonded.
No idea to be honest.
Perhaps open a ticket with their support? It has got a lot better in recent years.