Тоже долго мучался.
Решил на следующий день коренным образом.
Выпилил все Mail-настройки из .env
И вписал в config/mail.php следующее:
'driver' => env('MAIL_DRIVER', 'smtp'),
    'host' => env('MAIL_HOST', 'smtp.yandex.ru'),
    'port' => env('MAIL_PORT', 587),
    'from' => [
        'address' => 'user@yandex.ru',
        'name' => 'Type What You Want',
    ],
    'encryption' => env('MAIL_ENCRYPTION', 'tls'),
    'username' => env('MAIL_USERNAME', 'user@yandex.ru'),
    'password' => env('MAIL_PASSWORD', 'secretpass'),
Аналогичны настройки и для отправки с Gmail.