A communications system may include at least one wireless communications device and a plurality of electronic mail (email) servers for storing email messages for the at least one wireless communications device. The system may further include an email relay server for detecting a new email message on a given one of the email servers and, based thereon, sending a short message service (SMS) notification with a unique server identifier (ID) of the given email server to the at least one wireless communications device. The at least one wireless communications device may detect the SMS notification and send an email retrieval request to the email relay server instructing the email relay server to retrieve email messages from the given server based upon the unique server ID.