Spammers have SPF and DKIM set up for their domains, too. Why does it seem so impossible to you that if mail hosters see "this IP block hosted a lot of domains that turned out be spammy" they react with "block it" or at least "block it if new sites pop up there"? (and as a private user, you're often enough "new" because you don't send all that much mail)

Yes, it'd be nice if they didn't do that, but small sites are and will be acceptable collateral damage to them.