The modifying of sender addresses part would alone be done if there wasn't (enough) domain validation in place, to ensure the customer<->domain relation.
And as I believe I already added in #off-topic last week, from what I see, it does indeed look like you're doing very well regarding preventing outbound spam / junk from happening from your network, unlike many others out there.
Should I choose a provider based on e.g. spam / junk parameter alone, you / your network would definitely be a good candidate.
No doubt about that specfiic part!
It is however purely the domain validation part (or stuff similar to that), that I've trying to suggest you alternative ways "to limit the collateral damage (or even completely mitigate it)".
That said, if you got any questions or whatever, regarding any parts of those suggestions I've made, or otherwise want to discuss them further, feel free to poke me as well.
