Mail autocomplete is different for search and compose
The difference in autocomplete stems from the fact there is no “Mail knows about”. The lookup happens on two different sets of data:


Autocomplete in search happens on the Spotlight index of all received and sent mails in Mail.app’s database (since version 2 of Mail.app).
Autocomplete on compose happens on Mail.app’s potential recipients list, which is a compound of contacts with an email address in Addressbook and a list of previous recipients stored by Mail.app (a list you can see and edit under Window » Previous Recipients).


Notice the difference: search knows about people you have only received mail from, compose does not. Hence different autocomplete results.