Methods and systems for LLE encrypting and decrypting voice message streams (VMSs) already supporting eTe encryption are disclosed. In one example, LLE and eTe encryption initialization vectors (EIVs) are interleaved such that an LLE EIV retrieved from one of a header and a data unit is used to LLE decrypt both the header or data unit and a subsequent data unit. A recovered eTe EIV is used to eTe decrypt voice payloads in one or more subsequent data units. In another example, a base station dynamically LLE encrypts a VMS already supporting eTe encrypting by determining whether a received VMS is eTe encrypted, and ii it is not generating a new LLE EIV, and if it is, re-using the pre-existing eTe EIV for LLE encryption. The LLE encrypted (and perhaps eTe encrypted) VMS is then sent over the air to one or more mobile stations.