I run a mail server on my Linode and have never had trouble sending mail. It's easy to see if you're on a blacklist and take corrective action, though I've never had to do this.
I recently switched from Postfix to Exim4 and like it a lot more. The spam checking is much better integrated and lets you reject messages at DATA time with full spam information, so real messages that are auto-rejected at least bounce with an informative message.
Finally, if you don't like delayed mail, get a backup MX. It's very easy to set up for your friends that run their own primary MX, and you can return the favor. (I buy a backup MX service, but run backup MX for people that have asked.)