It absolutely matters which provider you choose, assuming the provider is big enough to have their own address allocations (which is not that big, really — plenty of relatively small hosting providers all over the world have their own ASN and address allocations).

My recommendation is to use a provider that doesn't host spammers. Hetzner is not great at that in my experience, but sounds like they've been fine for you. Smaller providers who know their customers and are able to pay attention to how their network is being used are generally quite good at making things difficult enough for spammers that they go elsewhere.