Check out a project I'm working on: hellocreature.com. We have a rails plugin you can use (or you can just use our REST api) to send emails that are signed with DomainKeys and DKIM, and are stamped with HashCash. We also support SenderID, SPF, etc. We also have standard pricing that is lower than those other companies' highest volume plans.

We're obviously in beta now so the site's marketing copy has a bit of work needed yet, but I'd be happy to get you set up today for a free trial. We've been having superb deliverability with our clients so far and we have a bunch of other nice features you may want to use.

Just email me at matt (at) hellocreature.com