For a good long while (months) we have had similar issues with various Verizon destinations.

Only Verizon Wireless destinations, or other Verizon Business things?

As of today, I'm told (via an upstream provider) that Verizon Business says this is a Verizon Wireless issue.

-- 
Richard