Along this path, check to see if their home internet IP address is blacklisted. Verizon's servers might be seeing the IP on one of these blacklists and silently dropping the message. These two sites cover most of the common spam blacklist services.

http://mxtoolbox.com/blacklists.aspx

http://www.spamhaus.org/lookup/