I don't expect this to be solved soon but some of Yahoo's DNS servers are out of whack.  I changed the IPs of some nameservers of some domains and now most Yahoo users can't e-mail to those domains!

As you can see below by the "No MX or A records for mychangedomain.com", now Yahoo's DNS/mailserver DNS cache is wrong.  You would think they would at least have cached the old incorrect records, but instead for some reason their DNS cache has no entry and doesn't seem to want to update itself.  Hotmail and Gmail all work fine, and some Yahoo users (probably on different nodes with different DNS) are able to e-mail me.  These DNS changes were now done over 2 months ago so it's not simply a matter of slow propagation time to Yahoo DNS Servers.

I'm sure that I'm not the only one, other sysadmins who have changed nameservers IPs may have noticed this.  Basically when you send an e-mail to the affected domains you'll get a bounceback like below (it may take minutes, hours or days to get the bounceback).

This is a real annoyance since many people use Yahoo mail.

I actually contacted them about it and nothing was done but I did receive some sort of template/automated response that the issue was forwarded and escalated.  I never heard anything further for days and then I sent followup e-mails and not only were they ignored but suddenly my Yahoo mail account was inaccessible.

Failure Notice
...
From:   
"MAILER-DAEMON@nm19.bullet.mail.ne1.yahoo.com" <MAILER-DAEMON@nm19.bullet.mail.ne1.yahoo.com>  [Chat now]
...
Add to Contacts
Sorry, we were unable to deliver your message to the following address.

<user@mychangedomain.com>:
No MX or A records for mychangedomain.com

--- Below this line is a copy of the message.

Received: from [98.138.90.55] by nm19.bullet.mail.ne1.yahoo.com with NNFMP; 28 Mar 2011 08:41:39 -0000
Received: from [98.138.87.2] by tm8.bullet.mail.ne1.yahoo.com with NNFMP; 28 Mar 2011 08:41:36 -0000
Received: from [127.0.0.1] by omp1002.mail.ne1.yahoo.com with NNFMP; 28 Mar 2011 08:41:36 -0000
X-Yahoo-Newman-Property: ymail-3
X-Yahoo-Newman-Id: 85723.72865.bm@omp1002.mail.ne1.yahoo.com
Received: (qmail 42791 invoked by uid 60001); 28 Mar 2011 08:41:35 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1301301695; bh=wx4RiKYlHcoyZoYUjZHx8K6MF8wQ1K/sbLsQjPLE5fI=; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:MIME-Version:Content-Type; b=duaEA/s3E70zLsLXgcHeILphV9fGNuHEIqV48rEIBzGFNd8gPyAxOXO5tKI2zO1EM8OBzd1Ou8VzfqF3vvrhYSGzt75O77/8flKR4IRmaUXwlzNHtp4oAKiDumZ879lHl7VOraxI13IM6CdKeATCEYM06Msfb5aosC4mHa1c6Is=
DomainKey-Signature:a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=yahoo.com;
  h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:MIME-Version:Content-Type;
  b=2qG7JakvDlcjFHS9vFXNmqab4QgyFrOkMe0eLUoXPssnnBG02sjzLMHFi1GRGs98cp79leYqHO6yYDXUBvgtiZSrrRYrXFuqfizKsLny9zJ5bQMMq4T4U9vtmNFXvL9Xk7tMtY0DZtegjinomTOVpKua18hS4XgiWYjT9gEFTvI=;
Message-ID: <879745.46782.qm@web121610.mail.ne1.yahoo.com>
X-YMail-OSG: PTsb7J4VM1n3oxK5NWarlmnFuvB5Y7RUEpEwGcKVbkB04D1
PBHJG_VPG.LWruo8SSbcUFN4vLR6Af1WLJTBZdqcBDyPejFfqYX13wqZwMHq
OIdgxtoApIixpHmBBaBunDAcEX.HVVGgI4amFS6ZQK4BAx0xzyP0bmBFPOvO
3K6k23pTJkWD_25X113W2r0j2ryNTE9JwIVWxEepLdiEImFt0DAsnxbnE2zX
oKsVh4hYsVrv7ciLPBPDUhtbuZPPBiV0B_izYKV0IUJnlSJ066ny4Ipm9cd1
MRhoYVDkwWIJo9T_GUP7KDirCnY9vbBLgyuXJ3u7fkA--
Received: from [] by web121610.mail.ne1.yahoo.com via HTTP; Mon, 28 Mar 2011 01:41:35 PDT
X-Mailer: YahooMailRC/559 YahooMailWebService/0.8.109.295617