A communications system may include at least one data storage device configured to store electronic messages and record identifications (IDs) therefor in respective accounts, and a plurality of mobile wireless communications devices each associated with a respective account. The system may further include at least one polling server configured to perform polling requests of the at least one data storage device and retrieve therefrom respective record IDs for each account, with each polling request being for a selectable number of record IDs. The polling server(s) may also be configured to selectively change the number of record IDs in each polling request based upon an estimated number of electronic messages stored in a respective account, and cause electronic messages to be delivered to respective mobile wireless communications devices based upon the record IDs.