I recommend you find a friend, or friend of a friend who does sys admin work at a company or school, who uses Linux and one of the common MTAs -- sendmail, exim, postfix. Pay them a flat monthly fee to handle your email, and do whatever they tell you, get a VPS or hosted service or linux machine on a cable modem or whatever. Pay them until you can afford to have a "real" setup, and in the meantime focus on making your startup work.

Personally, I would put a light weight (cpu and bandwidth will be minimal) linux server on whatever is the cheapest way you can get a business class fixed IP. I use exim.

When olefoo said keep the MTA and web operations separate, and you asked "with a queue?", I think olefoo meant keep them on separate servers. The MTA and web operations are normally separate daemons that run, and the web submits an outgoing mail to a queue in the MTA, but it's not somethingk you have to write or set up, it's the default way an MTA works.

When olefoo mentioned keeping incoming and outgoing MTAs separate, that might be a good idea but I would warn that if your account notification email comes from a different IP address than is listed in your MX record, some of those emails won't get to users because they will be blocked, dropped, or spam-foldered.

Once you start having to deliver lots of email, you will find that there is an incredible amount of pain in doing it reliably. You have to regularly examine all your bounces, and check for successful delivery to test accounts at the big places such as yahoo, gmail, and hotmail. First, you will have to make sure your From: and other headers are configured exactly correctly. Get a reverse DNS record correctly set up. You will probably have to learn about SPF records and domain keys and stuff like that. It can be a chore.

I still have problems with it. I have fixed IP addresses from a business class Time Warner connection, and I have had those IPs for a couple of years now, and some spam block lists still list me as "dynamic" ips, even though I have been through the removal process over and over. I have given up on ever being able to deliver mail reliably to earthlink addresses.

I run an email server on a VPS for my own use. I run Postfix [SMTP], Dovecot [IMAPS], and Procmail [email filtering/sorting]. I think it would certainly be affordable for a startup.

I've also, at some point in the past, looked at 90% of the email hosts out there, and tried my fair share. (And found none satisfactory to my (admittedly stringent) requirements.)

Email me, and I'll try to share what I've learned with you. (kngspook, gmail, you know the drill...)

I can heartily recommend postfix http://www.postfix.org/

It's a good idea to keep a logical separation between the sending MTA and the receiving MTA (separate hostnames at the least, separate machines/instances is best because you can manage security policy better).

Do plan on keeping the SMTP operations separate from the web application, and if your application is going to read email, plan on building spamfiltering in from the beginning.

What do you mean when you say "keep the SMTP operations separate from the web application"? With a queue?

It's more about maintaining separation of concerns, back in the late '90s I dealt with a web app that was written as one massive perl CGI that was called from the webserver and from the web users .forward; it was ugly, buggy and if you added the right headers to your email you could do sql injections.

Run the mailreader as a separate user, have it talk to the data layer on it's own, basic informational hygiene.

I recommend looking at postfix and qmail -- they were both written by people who understand security, but there are significant enough differences in their configurations that most people like one or the other but not both. De gustibus non est disputandum and all that, but it's worth looking at both so that you can decide which taste you prefer.