This issue was caused by an issue with monitoring data being delayed by our cloud provider, causing our automated alerting to think that the service was unavailable. The verification service was actually unaffected and available the entire time.