I never got blacklisted using the same domain and server for more that 4 years now. What was your provider? Sometimes you get an ip address that is blacklisted already... I use Hetzner or Privex