How Do Social Networks Handle Email Notifications?

Run a small but fast-growing social network and we're getting to the point where our email notifications (e.g., SoAndSo Added You as a Friend) isn't scaling and we need to find an alternative solution. We're going to be sending out 1,000+ notifications a day and one option would be to run Postfix (or something similar) on our servers. Of course the challenge with this is message delivery. Our concern is that even if abide by strict protocols and give our people unsubscribe options we'll still get listed as Spam. Some of the hosted services seem to have solutions that help with this given that they have good relationships with major ISPs, email hosts, etc.