I briefly read through K-9 Mail source code and found out that they enable TLS 1.2 on API16+ devices (as mentioned here).
@AndreaStC, try using K-9 Mail app for your mails, as the default mail application is too old and does not support modern encryption protocols.