It happened to me when one of my email hosting company's black listing services "lists" decided that the IP address of one of LO's servers was to be blacklisted. The IP address was blacklisted for a user 10 years before LO "bought" the IP address for the server.
It could be that your email client picked up something similar. If one of their lists shows that one of LO's IP addresses should be blacklisted based upon previous "users" of that address, then most of your emails to the list will not get through. Also your service can reject receiving emails from our servers as well.
You might want to contact your service and see if any IP addresses in your headers are in one their black lists they use. Maybe they can add LO back in a white list.