Yahoo Mail: "No mx record found for domain"

Solution 1:

The technically correct answer is that Yahoo! is at fault for not following the RFC. The real answer is to go ahead and create the MX record.