Call Yahoo and scream your heads off (politely).

I'm serious. Hotmail was willing to work with us to help us get things working. If you've already jumped through all the silly technical hoops, have a legitimate case for sending the emails, and comply with their terms, try to get through to someone at Yahoo. They have no vested interest in keeping legitimate emails from their users' inboxes.