Hi there, for me it was an issue with the Outlook servers. Because Outlook saw the email request coming from an external application (wordpress) it flagged it as spam. I needed to update the txt records within my server to include Outlook. It has since been working normal!
I am having the same issue, and have gone through the following steps like you:
I started having problems with the notification emails for the new orders / canceled orders in Woocommerce.
It happened before updating to the last version of WordPress and it keeps on even after.
I installed the WP Mail Log plugin to check that emails are sent and as far as I can see from the log they are working fine but still my clients and me cannot receive any.
My email is working, I contacted my hosting/provider and we checked together that everything is working. I tried to send an email from my personal address and it works.
I would love an answer on this topic as well.
