1) block outgoing port 25 to everything but their own mail servers;
2a) add an optional feature in each customer account to reopen outgoing port 25;
2b) add an optional feature in each customer account to pick the reverse DNS entry;
3) tell every other ISP/mail servers operators what they have just done,
so they get un-blacklisted since they won't be sending much spam any more.
This should block most of the outgoing spam without any side-effects,
since power users will still be able to operate their own mail servers,
complete with reverse FQDN. Non-power users won't notice a thing.
Also, they will save money on bandwidth to the outside world.
That's what my (strictly residential) ISP has been doing for almost a decade.
Works perfectly well for everyone involved.