I have "don't keep copies of any messages" checked, but I still want to be able to search header subjects. Can you not do this in mail.app? You can in Thunderbird and it works pretty well.
Obviously if mail.app isn't keeping copies of the message itself the body isn't searchable, but there's no reason the headers themselves couldn't be? Is there a third-party plugin for this?