Пока я два дня ковырял exim - у меня сложилось мнение, что это самое простое, что может быть. Он работоспособен "искаропки".
В вашем случае нужно будет поковырять роутеры, но по четвёртому пункту вот вам свеженькое хауту - http://welinux.ru/post/5311/.

Для начала стоит вкурить до полного просветления эту статью.

Теперь по пунктам:
1) Почму с провайдера почта забирается по pop3? Честно говоря, ни разу не видел чтобы это решалось именно так, хотя можно чуток поизвращаться с dovecot. Проще всего будет указать на сервере провайдера куда надо пересылать почту.
2) Это работа dovecot, либо другого pop/imap сервера.
3) См пункт 2.
4) Postfix, Exim, Sendmail.

P.S.: После того, как придет понимание работы всего этого дела, после реально работающих и настроенных собственноручно MTA и MDA, можно все снести и поставить Zimbra, но только ПОСЛЕ ) Так как если поставить сейчас, то будет сложнее разобраться как все работает, да и вряд ли появится желание.

P.P.S.: Если на "мастдайной машине" все работало, зачем было переходить на неработающую Ubuntu?

Вроде бы fetchmail умеет забирать почту по pop3 и раскладывать локальным пользователям, в зависимости от заголовков. См http://www.gentoo.ru/node/21003 например, правда там свою проблему не решили, но идея понятна.