IMAP supports server side searching. IMAP also supports custom flags (similar to GMail's labels) which can also be searched on. However, unfortunately, most ema

IMAP supports server side searching. IMAP also supports custom flags (similar to GMail's labels) which can also be searched on. However, unfortunately, most email clients don't seem to support IMAP custom flags (Evolution and Thunderbird do). I use Evolution with custom flags and virtual folders + imapfilter to automatically add custom flags. It works great.