Furthermore, you need to pick a host that takes action when their IP addresses appear on blacklists. Microsoft, particularly, uses UCEPROTECT as a blacklist source, and that particular company will blacklist and entire ASN if they receive too much spam from a particular IP address block (that doesn't get resolved in time).