If you don't want to store your mail locally, but want nice search functionality, for Google Mail users there's this patch:

http://people.spodhuis.org/phil.pennock/software/mutt-patche...

It'll do search server-side, which means that you have Google's full text search without storing mail locally.