When an Office 365 user account is deleted it is removed but any delegated access to shared mailboxes remains.

The script below will check all shared mailbox permissions and remove any that are for users who have been deleted.

# Remove deleted users shared mailbox access / permissions

# Connect to Exchange Online PowerShell
if ($Session.state -eq 'Broken' -or !$Session) { 
	write-host "Connecting to Exchange Online Powershell.."
	$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell/ -Credential (Get-Credential) -Authentication Basic -AllowRedirection
	Import-PSSession $Session -AllowClobber
}

# Get list of all shared mailboxes
$mailboxes =  get-mailbox -Resultsize unlimited | where {$_.RecipientTypeDetails -eq "SharedMailbox"}

# Check each shared mailbox delegate access
foreach($mailbox in $mailboxes) {
	# get list of users delegated full access
	$access = Get-MailboxPermission -Identity $mailbox.UserPrincipalName
	foreach ($permission in $access) {
		# Check user has \ character which deleted usernames have
		If( $permission.User -like "*\*" -and $permission.User -notlike "NT AUTHORITY*") {
			# display the deleted users
			$permission | ft
			# remove the permission
			Remove-MailboxPermission -Identity $mailbox.UserPrincipalName -User $permission.User -AccessRights FullAccess -Confirm:$false
		}
	}
	# get list of users delegated sendas access
	$access = Get-RecipientPermission -Identity $mailbox.UserPrincipalName -AccessRights SendAs
	foreach ($permission in $access) {
		# Check user has \ character which deleted usernames have
		If( $permission.Trustee -like "*\*" -and $permission.Trustee -notlike "NT AUTHORITY*") {
			# display the deleted user
			$permission | ft
			# remove the permission
			Remove-RecipientPermission -Identity $mailbox.UserPrincipalName -Trustee $permission.Trustee -AccessRights SendAs -Confirm:$false
		}
	}
}

Try running it first with the Remove-MailboxPermission/Remove-RecipientPermission lines commented out to ensure only deleted users are displayed. Then uncomment those commands and then run it again.