Here's my setup for that, in case anyone is interested: https://gist.github.com/45e318c68eb5a52e1646. It's essentially a cronjob (LaunchAgent on OSX) that calls a shell script to update the index periodically, plus a few macros to make searching from within mutt easier. To use this, you'll need to create a "Search" folder for maildir-utils to store results in.
mutt can also use IMAP/SSL directly, and I do that for some accounts, where I don't want to have local storage.