Hello,
What is the full error message that you receive from Verizon?
What is the IP address for your mail server?
What does the IP reputation for your mail server look like?
Is the IP address for your mail server on any blacklists?
How many emails do you try sending to Verizon users per hour / day / week ?
What percentage of those emails bounce?
Do you send to mailing lists?
Do you remove the addresses that bounce from your lists?
There are a lot of reasons why an ISP like Verizon may be blocking your email. Verizon usually includes a URL that helps to explain why the emails are not being accepted. Hopefully between the bounces and answering the above questions we'll have enough information to help you continue to troubleshoot and resolve the problem.