OK, we got MS support involved, and this was basically the resolution.
Install SMS netmon, provided by MS.
Activate all logging for IIS, Applog, SMTP. Start Netmon.
Send trace logs to MS.
Install SMTP connector, we were using just the default virtual server (which I may add was working fine...