Just an update on this.

Ended up chatting to the 365 admin from my friend's company who provided me with admin access also. Decided it wasn't a DNS issue, but seemed specifically related to their 365 domain tenant setup. Ended up logging a case with Microsoft, who after exhausting all local PC/Office Outlook possibilities, provided me with some PowerShell commands to run, the key one of which appeared to be:

"Set-OrganizationConfig -OAuth2ClientProfileEnabled $true"

after which Office Outlook then began accepting the password for each user and they were able to continue using their existing Outlook profile.