Kalau gmail biasanya paling cepat 2minggu bisa normal lagi. Dan juga bisa ajuin bulk sender kalo emang mau whitelist dan dipastikan sudah tidak ada spamming.
Kalau volume kirimnya belum besar, misalnya buat email pribadi atau notifikasi hosting skala kecil, bisa coba pakai AmazonSES. Tersedia 200,000 pengiriman email gratis.