Methods and apparatus for operating on a non-text (voice or fax) message include for each of a number of voice messages, searching each voice message for signal samples having one of a plurality of sets of pre-defined characteristics (such as any seven or ten digit number which is then assumed to be a telephone number). For each signal sample found to have one of the sets of pre-defined characteristics, the found signal sample is associated with an equivalent text string and this text string is stored in an envelope for the message. Based on a user input, the messages may be searched for a given text string and on finding a message envelope containing the given text string, such message may be operated upon.