Тут так же возникает такой вопрос: если подключить базу MySQL, то эффективно ли в одной таблице хранить более миллиона записей (например, о рассылке)?
Не там вы видите проблему.
Можно и 1 миллиард в таблице хранить.
А вот рассылать так, чтобы вас не забанили после чего сможете всего, к примеру, 100 писем в день отправлять
;))))