There could be several issues:
Are you properly disposing of your MailMessage objects? If you look, the object implements IDisposable and thus should be disposed of. (I would guess because of the potential attachments.) I would start here.
Have you talked to the server administrator. There could be some sort of throttling mechanism that detects you sending out so many mails in quick succession.
If you want to send you emails asynchronously and care about the result of the attempt to send, then be sure to register for the SendCompleted event. You will also want to store either the message itself or some representation to know which message was completed in the SendCompleted event. Keep in mind that the order things start in may not be the order they complete in.