1. An interactive method for composing an alphanumeric message using a telephone keypad, comprising in a messaging terminal the steps of: storing a received sequence of key codes that identifies a sequence in which keys on a telephone style keypad are pressed by a caller in order to enter the alphanumeric message; generating a word trellis from the sequence of key codes, the word trellis comprising at least one subset of candidate words recovered from a lexical database, each of the at least one subset of candidate words corresponding to one subsequence of the sequence of key codes; determining a most likely phrase having a maximum combined probability determined from probabilities stored in the lexical database, that comprises candidate words that are a combination of one candidate word from each of the at least one subset of candidate words; generating a most likely message from the most likely phrase and presenting the most likely message to the caller; confirming that the most likely message is the alphanumeric message; and editing the most likely message when, in response to the step of confirming, a message non-confirmation is received from the caller, wherein the step of editing the alphanumeric message further comprises the steps of: prompting the caller to speak an edit command; recognizing the edit command as one of a predetermined set of edit commands; and performing the edit command using voice recognition that is governed by a subsequence of the sequence of key codes.