A message status synchronization scheme. In one embodiment, a method may comprise: automatically detecting arrival of a message at a messaging server for a user having a mail address thereat, the message being displayable on a computer for the user with a status indicator icon associated therewith; processing at least a portion of an instance of the message for transmission to the user's mobile data communication device over a wireless network; receiving a status signal from the mobile data communication device indicating that the message has been deleted on the mobile data communication device; and altering the status indicator icon associated with the message on the computer responsive to the status signal.