I would advise doing it yourself. It isn't that hard, and assuming email is an integral part of your service, I wouldn't trust anyone else with it.
In terms of specifics, I like qmail. In terms of spam management, there are lots of things to do. First and foremost, have daily monitors on all the major email providers. Get on all their feedback loops. I've found that contacting them with problems is annoying, but does work if you are following all their guidelines and are persistent about it.
We've sent our own mailings out on a couple of occasions (to 4000 and 8000 users, respectively). And I've done it more often in the past, though for smaller numbers. I haven't had a bad experience doing it myself. A number of our customers are doing it regularly with phpList or poMMo.
There are a few things you have to get right (DNS including a PTR for your IP, SPF and now DKIM, RFC compliance in your server and configuration), but once that's done, bounce rate will be nearly as low as the quality of your list allows. Hitting the spam filters isn't all that bad either--assuming your message isn't spammy on other counts.
One other thing to be wary of: Sending to the same domain many times in rapid succession. Be sure you're not sending more than one or two messages at a time to Gmail or Yahoo or Hotmail (or any single server). So, randomize the list, and sleep for a second or two between each send, or something, to insure that there are pauses.
Oh, and at least Google's spam filters are reputation-based (and probably many others are, as well). The looser you play with the "opt in" requirement, the more likely you are to be flagged as spam by your recipients. It only takes a few to get your future mailings dumped into the spam folder. At that point your server itself is poisoned from sending to that destination for a while. So, make sure your recipients actually want what you're sending them.
Following the above, I was relatively spam free for about 3 and half years. At the high point of my last company, I was sending about a million messages a day. There would be spam flare ups of course, but I would get them resolved through persistent contacting of support staff. Now that I have essentially no users in comparison :), I'm not sending hardly anything, but I'm still monitoring and am not having any spam problems.
In my new services, I did have issues originally, especially on Gmail. So there was an initial ramp up with spam issues on the majors. But like I said, after following all their rules and then persistently hounding their support staff to investigate, I've gotten past their filters.
That sounds unreasonably low. You might have a different problem than just spam filters.
I've worked on several business that had to send confirmation emails (via our own servers), and the figures were never anywhere near as bad.
If there is any way that your users can benefit from signing up other users (e.g. if you run an MLM site), you might want to look into whether your stats are not being falsified by a few users submitting vast numbers of email addresses into your system.
I think it's unreasonably low too, but haven't figured out a way to solve it.
You can benefit by signing up other users, but this is not a very often used feature. It's not an MLM site, but a subscription chess service.
We track signups by ip and by browser cookies, so we're reasonable sure these are distinct people. Since we switched to the freemium model, there is little incentive for people to make duplicate accounts now, so I was hoping to see activation go up.
We do domainkeys and SPF and I have gone around the block with hotmail two times already.
We send approximately 25k emails a month, the bulk of which are sending out confirmation emails to people that signed up, and then a thank you for those that confirm. The rest are forgot password emails and invites.
The default qmail install will accept and queue incoming messages for accounts that don't exist on the system, and bounce them later (usually to an unrelated, innocent address) if the account isn't created.
Did you do anything in your installations to address that problem? If so, what was it?
In terms of specifics, I like qmail. In terms of spam management, there are lots of things to do. First and foremost, have daily monitors on all the major email providers. Get on all their feedback loops. I've found that contacting them with problems is annoying, but does work if you are following all their guidelines and are persistent about it.