A network device may include a memory to store a database including voicemail message information associated with a voicemail mailbox, a transmitter, and a receiver. The transmitter may send a notification to each of a plurality of communication devices, the notification including an indication of a number of new voicemail messages in the voicemail mailbox, an indication of a total number of voicemail messages in the voicemail mailbox, and an identifier of a most recent voicemail message in the voicemail mailbox, where each of the plurality of communication devices uses the notification signal to determine whether to request a list of voicemail messages. The receiver may receive, from one of the communication devices in response to the notification, a request for the list of voicemail messages associated with voicemail message information stored in the database. The transmitter may sends, to the one of the plurality of communications devices, the list of voicemail messages.