Sending email over internet

Users at my company cannot send email to another company over the internet. However we can receive email from them. I did a tracert and can only get halfway to the company (to their ISP), then I get “Request timed out”. I used trace software thatstates that ICMP is blocked at their ISP. Can anyone tell me — Does the problem have anything to do with ICMP being blocked? And if not, any other ideas why we can receive email from them, but cannot send email to them? We have no other problems with email.

Thanks in advance for your help.