Please define blasts and what the issues are for undeliverable messages. Have there been any discussions with their ISP about their business requirements?
Also, how many recipients are you talking about? Exchange has a limit on the number of recipients allowed. That number can be changed however. When you say they are not successful, do they get an NDR when they try? If so what does it say exactly? Are there errors in the event logs? If so what are they?
In Exchange System Mananger expand global settings, go to the properties of message delivery. You can change the maximum recipients there.