Har det fungerat tidigare i El Capitan? kan du komma på något som kan ha påverkat efter att det senast fungerade?
Om du söker på något lämpligt ord via Spotlight, kommer det upp några träffar ur epost då? Mail-appen och Spotlight använder separata sökindex, så det är alltså fullt möjligt att sök via Spotlight funkar fastän det är problem i Mail.
Angående manuell reindexering av Mail, min tidigare länk är lite gammal, i och med uppgradering till El Capitan flyttas data i den dolda användarmappen från mappen V2 till en ny mapp V3. Aktuell plats för indexfilerna är alltså ~/Library/Mail/V3/Mail Data. Det är de tre filerna som börjar med "Envelope Index" som du ska radera (läs spara undan på annan plats så länge). Avsluta Mail innan du flyttar filerna, sedan öppnar du mailappen igen. Räkna med att indexeringen kan ta ganska lång tid om det är mycket mail. Det kan slöa ner datorn, så gör det när du inte behöver datorn till något brådskande.
Tillägg: Förresten, om du misstänker att det är fel på Mails index-filer och vill jämföra, så här ser de ut hos mig med OS X 10.11.4. Storlekarna varierar naturligtvis med hur mycket mail man har. Alla filerna har skapelsedatum 2011-08-07, troligen då jag instalerade OS X 10.7 Lion och har ärvts och uppdaterats sedan dess
Envelope Index (10,1 MB senast ändrad idag)
Envelope Index-shm (33 K senast ändrad två dagar sedan - när jag senast startade Mail?)
Envelope Index-wal (915 K senast ändrad idag)