A method for managing incoming voicemail messages at a visual voicemail (VVM) system can include receiving a new voicemail message for a voicemail account associated with a mobile device, generating a deposit notification message at the VVM system in response to receiving the new voicemail message, sending the notification message to the mobile device, and receiving a request for voicemail message header information from the mobile device. The method can further include sending the voicemail message header information to the mobile device. The mobile device uses the voicemail message header information to determine a status for each voicemail message presently stored on the mobile device to identify the new voicemail message. The method can further include the VVM system receiving a request for the new voicemail message, and sending the new voicemail message to the mobile device for storage and playback on the mobile device.