Да, желательно отправлять отдельное письмо каждому пользователю. Кроме того лучше размазать отправку во времени. Обычно создают где-нибудь очередь отправки(например в БД) и постепенно опустошают ее, отправляя письма. Также есть уже готовые решения типа
phplist. А еще можно воспользоваться внешними сервисами почтовых рассылок, например
WebAsyst.
PS ни phplist, ни WebAsyst я лично не пользовался, так что отзыв об их работе дать не могу. Лично я всегда реализовывал эту функциональность через очередь в БД.