Blocking port 25 is not a real answer. It is not too difficult to set up a proxy and send the mail on a different port.
This is what Earthlink does to me ... they block port 25 ... yet in order for some of my customers to recieve my email the originating mailserver domain name must match the domain name I use as my email address
Here is an example as sent from earthlink
Outgoing server name = smtp.earthlink.net
Customer's server sees that mydomain.com MX records do not match to earthlink and thus rejects my email. ... and there is the case of some ISPs not allowing you to use your own domain name when sending email which is another problem all together.
Anyway ... what I have resorted to is setting up another port on my remotely hosted server to accept connections for SMTP.
This problem gets more complicated if you don't have the ability to control reverse DNS. Fortunately my hosting provider provides a control panel that allows me to manage reverse DNS for my domain and the IPs assigned to me.
There really needs to be a better and well thought out system rather than clampling unreasonable restrictions on legitimate users.