I seem to remember complaints before about failures sending to GMAIL. Have your recipients checked their SPAM/BULK/JUNK mail folders? I think there was some setup issue on LP mail accounts that GMAIL was very very sensitive to, and ended up treating almost everything from LP as spam. Anyway, have you searched this board for mentions of GMAIL, and problems related to it?
If other mail systems are being affected too, perhaps your server is on a spam blacklist. If mails are not being bounced as spam, though, I don't think there's anything that support can do. They need some sample bounces to find out who's reporting the server as a spammer.
Also check how many emails you're sending over time. Even if you stay under the LP limit (inbound and outbound) of 400 or less hour, some mail systems may still flag an "excessive" number of mails from one source as spam.