A video mail server comprises a video call signaling module coupled to an internet protocol network for establishing a first internet protocol channel with a caller remote internet video device to support a recording session over the internet protocol network and establishing a second internet protocol channel with a user remote internet video device to support a playback session over the internet protocol network. A media interface comprises a recording module for obtaining a recording sequence of compressed images representing motion video images from the caller remote internet video device and storing a video mail file representing the recording sequence of compressed images. Each compressed image frame is one of: i) an independent frame from which an image frame can be recovered utilizing only the independent frame; and ii) a dependent frame from which the image frame can only be recovered utilizing both the dependent frame and an independent frame preceding the dependent frame in the sequence. A play back module retrieves video mail file from the storage and transfers a playback sequence of compressed images to the user remote internet video device.