It looks to me as though Verizon is using yahoo to host their email services:
mta1012.vzn.mail.ac4.yahoo.com

yahoo has always had some pretty sticky anti-spam rules. My guess is that they're adjusting some things, and the dust hasn't settled yet. yahoo has so many mail servers that it's quite possible to see inconsistent behavior from one message to the next, depending on which servers process the message.

Trying to send from a different domain/server is a good suggestion, short of running your own mail server (where you have much more control of things).