This absolutely has an effect on email deliverability. I previously worked on a bulk mailing system (newsletters), and we had to be extremely careful about what our clients sent out to prevent our system ips from being compromised.
You should indicate to your ISP that you are not happy with blacklisted IPs