Если у вас возникнет такая же проблема, то попробуйте:
1. Поставить sendmail. У меня это было apt-get install sendemail
2. Прописать путь к sendemail в php.ini. У меня это такая строчка sendmail_path = /usr/sbin/sendmail -t -i
3. К яндексу получилось подключиться с encryption tls и 25 портом
4. Должно стоять расширение openssl. Если phpinfo() выдает, что openssl enabled и вы перезагрузили сервер, то это не значит, что расширение включено и работает. Это стало для меня открытием :( Нужно ещё прописать в php.ini extension=openssl.so