Have you tried instead of mail, using:
userPrincipalName
firstName
lastName
userPrincipalName (or WindowsEmailAddress)
If it were simply AD then mail would be fine, but when i connect to EXO and pull user information I do not see an "mail" attribute anymore. Here's how I got to this to try:
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri "https://ps.outlook.com/powershell/" -Credential $LiveCred -Authentication Basic -AllowRedirection
Import-PSSession $Session
Get-User -Identity "USERS NAME REDACTED" | format-list
NOTE: you will got a POPUP window to authenticate with your O365 account. If you do not have permissions to connect to EXO this way it will likely fail with a wall of red text with a buried permissions issue.