Exchange email being blocked by Yahoo.

Yes - Yahoo randomly block people for no reason - it's a pain in the ass.  After a lengthy discussion, they may eventually unblock you!
Please click on this link to communicate with them:
http://smallbusiness.yahoo.com/contactus/ 
Please also check that your house is in order by reading and checking against my FAQ:
http://www.it-eye.co.uk/faqs/readQuestion.php?qid=2 

Do you have reverse DNS, SPF, and DomainKey records set?  

This is not going to be easy, believe me I KNOW!!!!
When you try and telnet to their SMTP server does it say permenant fail?

You might want to check if you're not blacklisted with any other bl-players.
www.mxtoolbox.com
www.dnsbl.org
will do this for you ^^.

I checked the blacklist on mxtoolbox.com and it shows them as ok for all but 4 of the lists and csma, fiveten, nomorefunn, and spamrbl all show timeout instead of ok.  So far they only appear to be having trouble with yahoo.

Timeout is usually fine - I would take that as okay.

Where would I find the reverse dns?  Mx records say they are set up properly on checkdns.

Reverse DNS is something setup by your ISP on your fixed IP Address.  If the reverse DNS check passes - then it is set properly.
Essentially, the rDNS record should be something like mail.yourdomain.com and this should be the same as your mail server advertises itself as.

It shows a ptr pointing to the ip and the domain and lists their ISP on the record.  They do have a spam filter from postini but I don't believe that filters any outgoing mail, just incoming.  I'm still not seeing any way to get in contact with Yahoo about this, all their contact pages seem to be geared towards those who have a yahoo account.

When I look at the application logs on their exchange server there are several transport errors related to yahoo and all of them show the the error: "delivery to domain yahoo.com failed remote connection dropped" or "delivery to domain yahoo.com failed, remote server did not respond to connection attempt"
I don't see any other errors about any other domains so far other than yahoo, which is the only one they have reported.  I will see what yahoo says or if anyone knows what these errors mean if they can be fixed on this end, let me know.

Thanks Glen.

"delivery to domain yahoo.com failed remote connection dropped"
means that they are blocking you for one reason or another.
Follow Demazter's advice above - then book a flight to Columbia for a long weekend trip to go Coffee Bean picking, go pick your beans, bring them home, start grinding them, make some coffee and sit back and wait for a response!!!!

Thanks, I also found a phone number for them, called it, and got told to go to postmaster.yahoo.com and fill out a form there which I did so I will do this one as well and see what happens, appears to be on their end at this point.  We also recently had another client who used Iquest email and was all of a sudden getting blocked by hotmail and msn and Iquest had to get them off their list so maybe there is some new heightened security being put up.
Thanks

I think they have an IT Admin who gets bored and decides to randomly block IP's for a laugh, just for something to do !

Just emailed them again, haven't heard back since the first one 3 hours ago other than the automated response that it was received......

I sent that above form in twice yesterday and just got a response from them that they:
"We have made appropriate changes to the IP address you have submitted within our database. However, we cannot fully exempt your mail server from our SpamGuard technology. This should help with delivering mail to the appropriate Yahoo! folders.

Please be aware that Yahoo! Mail users are able to set their own preferences for the manner in which they receive your mailings. If the recipients of your messages want to ensure they receive your emails in their Inbox, you may want to ask them to set up a filter in Yahoo! Mail specifically for your emails, or have them add your email address(es) to their Yahoo! Address Book."

Gonna have the users test from their domain and see what happens if this fixed anything....

That's as good as it's oing to get!
That's what I got too!

And it started letting you send to yahoo after that?  Was there any kind of time lapse for it to propogate before it started working?

No, it just started working, you MIGHT find that the mail will go into the junk folder in Yahoo on the mailbox but at least it gets there.

Seems to working now, they just tested and it took a few minutes but emails from their domain showed up in a yahoo account, also ones they tried yesterday are there too so it looks like the ones that did not get out, kept trying to send instead of giving up after the first time, which is a good sign.  Thanks for your Help!

They will sit in your queues for 48 hours before they fail and exchange will continue to try during that time.
Glad you got it sorted.

Don't forget to vote for the guide if you found it usefull :-)