Mail Forwarding, ISP Denying access to port 25

A couple of my users have recently been denied to use my outgoing mail server. For some reason, the mail server I have on my box is better then a local High speed internet's ISP. The local company is blocking access to port 25 and I am wondering how do I get around that so end users can use my mail server as opposed to being forced to use the local companies....