Having just gone through the process of setting up a VPS to handle sending and receiving email, processing bounces and recording delivery receipts I'd say that, fundamentally, this isn't challenging.
Then again I've also setup my own SMPP server for sending SMS and didn't find that particularly difficult either :)
Some of the inbound processing features sound pretty good - how about offering them as a paid-per-transaction service? I wouldn't bother outsourcing the sending and receiving per se because it's cheap and easy to do that myself, and I then have control over the up (or down!) time but being able to pass a message through your service and pay, say, $1 per 1000 messages processed with no storage costs would be kinda cool.
I'm imagining getting back some kind of structured document (XML and/or JSON) allowing me to see quoted messages, interleaved replies, attachments, encoding blah blah basically all that stuff you're talking about.