May I ask what your clients are paying?
Maybe the answer is to charge them more instead of giving them a low price (an assumption on my part of course which is why I ask what you are getting for this) and some implicit guarantee of uptime.
For example we had some customers some time ago who were pooled on a shared IP address for sending SMTP service. Occasionally they would experience problems with mail reputation on that shared IP. If they complained about that would simply explain that that was the drawback of a shared IP and that they could always upgrade to a service level where they got a unique IP and could establish their own reputation.