Hi guys!
As per the issue documented in https://dev.gnupg.org/T3934, the same behaviour was experienced with the Mimecast for Outlook plugin.
Windows 10, Outlook 2016, Gpg4win (3.1.2), Mimecast for Outlook 7.5.2350.20950.
Update Gpg4win to 3.1.10 and the problem was solved.
Disabling the Mimecast for Outlook plugin solved the problem in the first case, after the update, the plugin could be reactivated and all was working.
Just my 2c if someone was having the same problem at some stage.