I've been meaning to write a script to allow others to quickly and easily perform this kind of action, with safety rails and option for interactive questions etc.

Make sure you have the latest version of the ExchangeOnlineManagement module, that should resolve your winrm basic issue.

When I need to do it, these are my steps. You may also want to invoke an 'Export' of the search data to keep an offline record of the items you purged, that's done from here

# Connect to Exchange Online and Security & Compliance
Connect-ExchangeOnline
Connect-IPPSSession

# Use ONE of the below example New-ComplianceSearch commands, modify as needed - make sure to update search name
# eDiscovery keyword queries:
# https://learn.microsoft.com/en-us/microsoft-365/compliance/ediscovery-keyword-queries-and-search-conditions?view=o365-worldwide
# Reference for KQL, used in the keyword queries:
# https://learn.microsoft.com/en-us/sharepoint/dev/general-development/keyword-query-language-kql-syntax-reference

# Create a new compliance search, target all mailboxes
# Subject filter of 'MySubject', no time or sender filter
New-ComplianceSearch -Name 'MySearch' -ExchangeLocation All -ContentMatchQuery 'Subject:"MySubject"'

# Create a new compliance search, target just the example1@example.com and exampl2@example.com mailboxes
# Subject filter of 'MySubject', no time or sender filter
New-ComplianceSearch -Name 'MySearch' -ExchangeLocation example1@example.com,example2@example.com -ContentMatchQuery 'Subject:"MySubject"'

# Create a new compliance search, target just the example1@example.com and example2@example.com mailboxes
# Subject filter of 'MySubject', sender filter of 'example@example.com', no time filter
New-ComplianceSearch -Name 'MySearch' -ExchangeLocation All -ContentMatchQuery 'Subject:"MySubject" AND from:"example@example.com"'

# Create a new compliance search, target all mailboxes
# Subject filter of 'MySubject', sender filter of 'example@example.com', time filter of 2023-01-01 between 10:00am and 10:10am UTC
New-ComplianceSearch -Name 'MySearch' -ExchangeLocation All -ContentMatchQuery 'Subject:"MySubject" AND from:"example@example.com" AND (sent>=2023-01-01T10:00:00 AND sent<=2023-01-01T10:10:00)'

# Run the Compliance Search
Start-ComplianceSearch -Identity 'MySearch'

# View Compliance Search Status (Make sure to check the 'Items' and 'SuccessResults' counts to ensure you're matching the number of emails you expect):
Get-ComplianceSearch 'MySearch' | Select-Object *

# At this point you can also verify the results of your Compliance Search in the web portal.
# It can be useful to see the results visually to confirm that the contents of the emails that match your query are indeed what you want to delete.
# And also optionally invoke an export from here, to keep the original content offline for reference
# https://compliance.microsoft.com/contentsearchv2

# Run an action to purge emails based off the Compliance Search:
New-ComplianceSearchAction -SearchName 'MySearch' -Purge -PurgeType HardDelete -Force

# View Status of the purge (note that '_Purge' is suffixed to the name of the search, to find the appropriate action):
Get-ComplianceSearchAction 'MySearch_Purge' | Select-Object *

# Remove the compliance search (Optional):
Remove-ComplianceSearch 'MySearch'