I've heard it's relatively common to get allocated an IP that has previously been abused by spammers, or certain providers will reject incoming mail from IPs that have no reputation (but then how can you build reputation?).