am being on 4.10.5 but this might assist you.

Following a discussion on kdepimusers mailing list I found a tool called nepomukpimindexerutility - run it from konsole or ALT+F2

It told me that most of my mail folders (despite having "indexinglevel 3" meaning indexed) were either not indexed at all or partially indexed. You can index or re-index a folder from a small menu called up by right-click.

After painstakingly indexing or re-indexing those folders I am interested in (eg I skip Spam and so on) I now have a way better hit-rate on searches. It (the nepomukpim...) does not automatically do sub-folders sadly (and I have quite a few) so had to click my way through my various folders and index/re-index each and every one.

What I have now noticed: newly arrived mail does not get indexed until next time you start KMail/Kontact. I can live with that though but clearly there is no "daemon" checking new mail in folders while KMail is running.