unlimited/multiple pop3/imap mail
multiple database MySQL
mod_rewrite, dunno the full capabilities of .htacess but blocking certain clients, image hotlinking and passworded directories is a must.
The ability to use multiple domains rather than buy and account and a name and be stuck like that.
Good stats, something you could query without having to work directly on the server log would be nice, maybe through a database or summit.