A communications system may include at least one destination server for hosting email message boxes, and communications devices for generating email messages each associated with a respective message box. A delivery server may have a plurality of queues and a controller. The controller may store the email messages in a first queue, and attempt to send the stored email messages to the destination server at a first sending rate. The controller may also move email messages stored in the first queue to a second queue based upon a delivery failure. Email messages may be sent from the second queue at a second sending rate less than the first sending rate. The controller may also move email messages from the second queue to the first queue having a common characteristic with a successfully delivered email message.