Проблем с антиспамом быть не должно кроме совсем суровых серверов, т.к. gmail прописывает все положенные заголовки подтверждающие подлинность отправителя и т.п. Но gmail не позволит отправить через него такое количество писем. Ограничение по-моему 500 в сутки.
Есть сервисы рассылок, но для уведомительных писем они по-моему не подходят, они скорее для отправки рекламных и т.п., когда один текст письма и надо разослать одновременно многим адресатам. Еще есть Amazon SES, думаю он подойдет, но с ним не работал и он естественно платный.
Рассылать со своего сервера в принципе можно без проблем, только надо немного озаботиться его настройкой. Если ваш почтовый сервер exim, то вот этой статьи хватит как минимум для начала:
habrahabr.ru/blogs/sysadm/114852/.
Еще момент, если писем приличное количество и отправляет их сайт, делайте отправку писем асинхронной, иначе передача их мейлсерверу может надолго затянуть ответ пользователю
