> мне приходит success, а значит письмо отправилось, верно?
не верно. это значит, что скрипт вернул success, а отправилось письмо или нет — смотрите в логах, дебажте
ну или без SQL.
Набиваете массив строк (от 0 до к-во строк в файле). shuffle этого массива, потом считываете по одному значению из массива, читаете этот номер строки, записываете в новый файл.
Не забудьте сохранять позиции начала строк, относительно начала файла. 10 минут дела.