Tell their users "I'm sorry, but there is nothing we can do to send you the mail - please complain to Verizon."

If enough users complain, they might change their policies. Ehh, wait, we talk about Verizon here.

Don't bother.