Clearing cached recipient addresses in Mac OS X Mail
In Mail, choose Window → Previous Recipients. Mark the ones of interest and press Remove From List.
Search problems in Mail (Mac OS X Lion) solved
The other day I noticed the search function in Mac OS X Mail (Lion) wasn’t turning up email I know I had somewhere in some mailbox. This was quite irritating since I knew (roughly) the contents of the email and needed to get it but I didn’t know when I had gotten it.