I've been using Mutt for several years now, after a few years of Pine and a short stint with Elm. Mutt is highly customizable, stable, actively developped and should meet all your requirements.

Borislav