WordpressMU in AWS just won't send emails

Hey all.
Got a Wordpress Multisite Bitnami HVM (bitnami-wordpress-4.5.2-0-multisite-linux-ubuntu-14.04.3-x86_64-hvm-ebs-mp) on AWS, EC2, t2 micro that is configured to create multiple sites and does so OK, (thanks to your awesome previous support).
My site just won't send any emails.
I tried to configure two separate plugins for this: WP-Mail-SMTP (pre-configured with the Wordpress AMI) and Postman SMTP currently installed and activated.
I tried ALL the possible combinations for:
a) simple php mailer,
b) SMTP via Google, Microsoft and Yahoo credentials using login (username / password, e.g.: SMTP-STARTTLS to smtp.gmail.com:587 using Password (Plain) authentication.) and paid attention not the mess withe SSL, TLS and STARTTLS settings,
and
c) SMTP OAuth 2.0 with Client ID and Client Secret (created for a MicrosoftAPI app and for a GoogleAPI app - I did reset the plugin before switching from OAuth to the other).
The Postman SMTP tests the connectivity with the mail servers (SMTP servers) and all the tests work fine. Both of the plugins work fine and accept all the configurations that I described above.
The issue is that after successfully configuring both plugins I tried to send test emails from both plugins and I get notifications that suggest that wordpress cannot access the mail servers (authorization failed - and believe me I have checked multiple times in all of the platforms that I have the right credentials)

Particularly from configuring with Yahoo I get:
********
5.7.0 (#MBR1212) Incorrect username or password.
*******

From configuring with Microsoft I get:
*******
5.0.0 Authentication Failed
*******

From configuring with gmail I get:
*********
5.7.14 <https://accounts.google.com/signin/continue?sarp=1&scc=1&plt=AKgnsbsE
5.7.14 Z2Mx7qyu6EvxY-Ia091d0Sgk8cOTKqtUI09qVaxVFMvvLJwl7HEGVGa0C0fCZwFLxuYOze
5.7.14 oJaVDbh1A1MTOLhQxtPzR2yaVeNafNfzm0S287uHJ4lQz39kW9AglvvSZd5dTruLj9MkQD
5.7.14 ZgXQ732bhggueYYbr9fznZFoZk_xNWQVwYVHRCdaP7qUYXNs-ztwgB-GvkfNNQgmeNM8lf
5.7.14 RjTIimoCR9X1VCO8U7KkA5kl683Fc> Please log in via your web browser and
5.7.14 then try again.
5.7.14 Learn more at
5.7.14 https://support.google.com/mail/answer/78754 u64sm1439408wmd.8 - gsmtp
*******

What am I missing?