Microsoft Outlook on Android and the Phantom Contacts in Direct Share

Despite it reading like the title of a Harry Pothead book, it turns out it's Outlook email address suggestions causing the issue. The solution is to uninstall Outlook and use something else.