Ack. Same here. I had a mail server colo'd with Peer1 in Canada since mid 2000's, which I moved to a European colo few months ago. I use it to periodically send

Ack. Same here. I had a mail server colo'd with Peer1 in Canada since mid 2000's, which I moved to a European colo few months ago. I use it to periodically send newsletters to few thousand people, so it's not exactly low-volume. The one and only issue was with some AT&T block list - and judging by their supporting forums they end up with a boatload of false positives - I filed a complain with them and they removed the block few days after. I suspect that OP ended up getting an IP from a netblock that has lots of transient customers, which included some spammers. It's not his server's reputation that was weak, it's the netblock's rep that was bad.