Your problem sounds like it has nothing to do with sendmail, but with any IP traffic. Does the other company have a Web or FTP site at the same IP address or with in the same class C? If so, when email doesn't work, I bet neither of these work either. I've seen this happen before. The ISP isn't properly routing traffic between your two networks. I'm not sure you if you could put in a static route that would by pass your ISP's faulty routing tables or not. I'm betting probably not.