I basically need
- add new domain to my solution
- create new email addresses ( there will be more than 50 of them in the future per domain)
- forward everything from the new email address somewhere else. I guess I can redirect the email to make the whole solution easier and not to have real account on my linode at all.
- be able to send emails from my VPS box.
- it would be nice to be able read the emails via web interface if I don't redirect them and keep a local copy.
VPS would probably run Debian
Do yourself a favour and don't run qmail. Postfix or Exim are quite nice. Forwards can be handled either by locals files, mailbox forwards or virtual mappings in postfix (not an exhaustive list).
I would recommend exim as the MTA, with vexim as the admin frontend (is web based, and uses MySQL for storage). Vexim has nice features when it comes to administering mail servers with lots of domains, lots of aliases and catch-all forwarders.
Any exim installation in its default configuration can send mail from the server itself (I think pretty much any MTA will do that out of the box).
When it comes to the web interface, I would have to agree with Paul Tomblin. Squirrel will do the trick, but last time I used it (about 3 years ago), it had severe problems when you have more than few thousand messages in any one folder.
If you need an all-in-one solution, and you can afford to have a dedicated server for the task, you might want to check out Zimbra. Could be a bit heavy for your needs, but it definitely does all the tricks and has (apparently) a very nice web interface.
Postfix wil do most of that. One of the better features in your situation is that you can configure it to get the virtual address mappings out of an SQL database, which makes maintaining new domains and addresses a lot easier than the way I'm doing it, using flat files.
I've never found a decent Linux web mail interface. Squirrel is the most common, but it kind of sucks. I tried a more modern looking one that used AJAX, but it got me hacked so I dumped it. So I installed dovecot and I read it using Thunderbird or the mailer in my phone over IMAP.