There is a need in voice-messaging systems for a feature that allows the user to control the speed of message playback. This capability is generically called “time-scale modification” or TSM within the speech-processing industry. There are many methods of implementing TSM, but the best of them allow the subscriber to stop and start playback as well as to slow down or speed up the message playback by a factor of from 0.5 (half speed) to 1.5 (1.5 times normal speed) while maintaining the fidelity of the original recording played at the original real-time speed (normal speed). The user usually controls the speed by pressing DTMF digits on a telephone handset, ASR (Automatic Speech Recognition) voice commands, or pointing devices on computer-based terminals.