I came to know that our DKIM was set to Inactive post the upgrade that caused this issue for us. It's unfortunate that NetSuite don't have an audit trail / system notes recorded for the email preferences. This means we don't know if was done by a user or if NetSuite did the inactivation after the 2019.1 upgrade - most likely it is NetSuite messing it up after upgrade but they were not ready to accept this ofcourse.