The License Retrieval service is up and running. We still have the 250 limit issue and we are working to circumvent that problem.
As is often the case, the problem had nothing to do with the suspected cause! It appears that about 24 hours after we started using Yahoo's internal sendmail service, Yahoo had a system wide problem which affected all customers. It took them 24 hours to realize that there really was a serious problem then more time to realize that problem was the root cause of our issue.
The problem is not fixed but they gave us a work around that is working for now. As I mentioned we are working on a solution that will eliminate this path all together.