Может быть несколько проблем:
Правильно ли вы избавляетесь от своих объектов MailMessage? Если вы посмотрите, объект реализует IDisposable и, следовательно, должен быть утилизирован. (Я думаю, из-за потенциальных вложений.) Я бы начал здесь.
Вы говорили с администратором сервера. Может быть какой-то механизм регулирования, который обнаруживает, что вы отправляете так много писем в быстрой последовательности.
Если вы хотите отправлять вам электронные письма асинхронно и заботиться о результате попытки отправки, то обязательно зарегистрируйте событие SendCompleted. Вы также захотите сохранить либо само сообщение, либо какое-либо представление, чтобы узнать, какое сообщение было завершено в событии SendCompleted. Имейте в виду, что порядок, в котором все начинается, может не соответствовать порядку, в котором они завершаются.