На сколько я знаю (тоже однажды сталкивался) у Яндекса есть защита от спама, поэтому можно отправлять определенное количество одинаковых сообщений в определенный период времени.
Попробуй отправлять по девять-десять штук (или одно сообщение на 9-10 адресатов за раз, если это подходит) с промежутком в пол часа или час. Если станут доходить все, то точно эта защита срабатывает.
На mail.ru тоже есть такая фишка но там по-моему условия мягче.