Your host may be employing new methods to thwart spam.
Are you sending your messages with SMTP or "Internal PHP mail"? (Note: Confirmation, welcome and some notifications are always sent with PHP mail)
Each method sets the headers a bit differently, and there is a fix for setting the correct "Return-path" (bounce address) on some servers. (enable $phpmailf=1; in config.php)
Is bounce enabled, with the "bounce to email" set to an address on the same domain as ListMail is installed on?
Not using an address @ the ListMail domain for the "bounce to email" can cause sending problems. Generally the "Send From Email" for each list is much less restricted and can be anything you want, even @ another domain, however some servers further restrict this, forcing it to need to match the bounce / authenticated address.
Are you using the "AUTH" feature to authenticate with the server?
This may or may not be required. Typically it's good to authenticate with the bounce address, but if that is forwarding to bounce.cgi you should also be able to use another account on the same domain.
Often an SMTP host setting of "localhost" with no AUTH will work for sending your emails, however your host may shut down this avenue unexpectedly. In that case I would check the bounce settings and try authenticating with any account.
Regards