For anyone reading this, just a quick update...
We ended up creating an emergency support ticket over the weekend and firstly I'll say that the support received was tremendous - so kudos to the SM team, including Von-Austin who handled the ticket and Derek & Tim for commenting in the community on the weekend.
Our main issue with undeliverable emails has been corrected. However, figuring out exactly what happened & why is looking more like a plane crash in that there were probably several factors, some related and some unrelated, contributing to the problem. It was a mixture of the software behaving differently than in previous versions combined with (mis)configuration settings. To their credit, SmarterTools committed to refunding the full ticket because there was it least some elements of this caused by a bug.
In our case, one of the contributing factors was that our SmarterMail installation had been running on a server for about 5 years or so, moved to a different server, and has been running on that server for a few years now.
We also have integrated our own custom built CMS solution to SmarterMail via web services to manage users & aliases for each of the domains we host both the website and email for. A few years ago we noticed that it was possible to delete the primary administrator account for a domain using the web services. That didn't prevent the domain from working but it caused some strange issues from time to time when doing various things. If one of our customers did that and noticed strange things, we'd fix it for them by re-assigning a primary administrator.
In at least a few of the domains that were having deliverability issues with the latest minor, we discovered that the domain didn't have a primary administrator set, which prevented the UI in SM16 from working properly when managing the domain.
On top of that, most domains did not have the IP4 address set for the domain (which I think is the correct setting), but some had the IP of the new server, and some had the IP of the old server. The ones that had the IP set to use the old server for outgoing were the ones causing undeliverables. Setting the IP for outgoing as either not set or as the IP of the current server fixed the issue.
So there probably was something within the latest minor SM16 version that started to use the Outgoing IP setting defined at the domain level rather than using the global setting for the server. The old behavior may have been by design or a bug, and the new behavior may be by design or a bug - but in any case the behavior changed which is essentially why this started after installing the latest minor.
We're still working towards a full resolution to identify all the contributing factors here and how to both correct potential misconfiguration as well as prevent future misconfiguration. One thing in particular which we should have logged as a bug a long time ago was that the web services allows the primary administrator to be deleted - something that's not possible to do within the UI of SmarterMail itself. We corrected that in our own implementation of the web services and forgot to file a bug report. Lesson learned!