Hmmm, I use https://njal.la/ for DNS. Could spamhaus really just auto-mark every njalla user as suspicious?

Yeah, possibly. Privacy related services are often used by spammers.