O IMAP é praticamente a única escolha, sim. Ele mantém todo o estado da mensagem no servidor, permite organizar o correio em pastas e praticamente todos os clientes de correio o suportam, geralmente com atualizações em tempo real.
Para dispositivos que não o fazem (por exemplo, se tiverem apenas um navegador da Web), há também alguns clientes de webmail que usam o próprio IMAP, como o RoundCube, o SquirrelMail ou o IMP da Horde.
Ainda não experimentei muitos servidores IMAP, mas até agora o Dovecot funcionou muito bem para mim. Os servidores IMAP geralmente não podem buscar mensagens de outros lugares; eles esperam que ele seja entregue por um MTA como Postfix ou Exim ou Sendmail (que recebe e-mail por SMTP) ou por programas como fetchmail ou getmail (que baixam mensagens de outro servidor IMAP ou POP3).