An apparatus, program product and method utilize voice recognition to process voice messages in an automated manner to detect spoken numbers contained therein. Detected spoken numbers can then be utilized to set a start position at which to begin playback of a voice message, e.g., to permit a user to locate and transcribe a telephone number spoken by a message sender. Automated number detection may also be utilized to automatically dial telephone numbers mentioned in a voice message, as well as in the display of textual representations of such numbers to a user.