There is currently no way to do this. Thunderbird's autocompletion can only match the beginning of each field of the contacts in your address book.
A bug has been reported and there are plans for improvement, but no solution has yet been released.
Note that there are some cases in which it may look like Thunderbird is performing substring matching, when really it is still just matching the beginning of other fields. For example, if you had the following contact in your address book,
Email: [email protected]
Work Organization: Icecream Factory
icecream in the To field would autocomplete to
[email protected], but only because it matches the beginning of
Icecream Factory. This behavior may be what you remember seeing in the past.