EugeneOZ

А в чём выражена потребность удаления? Объём более, чем скромный. Из-за чего их дорого держать?
Почтовые адреса нельзя проверить по отчётам почтовых серверов и заголовкам их ответов. Для проверки заведите себе ящик на rambler и пообщайтесь с почтовым сервером.
Регулярками можно срезать много валидных адресов, т.к. по спецификации перед @ может быть что угодно, ограничение только по длине. Погуглите — на SO есть известные ответы на эту тему.

Вы очень поверхностно описали вопрос.
Nginx + php-fpm очень рекомендую. Но самая главная замарочка — репликация/шардинг базы данных. Рекомендую читать не только на официальных сайтах баз данных (там всегда всё «быстро надёжно автоматически»), но и на serverfault, news.ycombinator.com. MySQL очень плоха в репликации, MongoDB тоже имеет с этим косяки. Про PostgreSQL хорошо отзываются (даже master-master есть), но я сам не пробовал на практике. Пробовал Couchbase — прекрасно кластеризуется, даже ребёнок справится, умеет кросс-датацентр репликацию. Но это NoSQL — бд нужно выбирать по задаче. Если больше подходит именно rdbms, то лучше PostgreSQL, imho :)
Ещё вам понадобится кластеризация кэша — как варианты: Amazon ElastiCache, Couchbase, Riak. Через несколько месяцев будет Redis Cluster :)

На одной vps не храните несколько разношёрстных сервисов. Например, сервисы, которые по крону будут делать долгие тяжёлые задачи, лучше вынести на отдельную vps.

Ещё рекомендую сделать api для внутреннего взаимодействия приложений, чтобы они не общались дру с другом, изменяя значения в «чужих» базах или таблицах.

1) Redis
2) Redis или MongoDB
что тут обосновывать — каждый кулик своё болото хвалит, всё субъективно :)