Jonathan,
Sorry but I disagree with Per. ISPs have a duty to prevent email Spam which is a terrible curse for us all. If they decide that blocking port 25 outbound will help then they should do it.
If you are a user, why can't you use the ISPs relay server? If you are a provider you ought to have your own mail server on a fixed IP address.
You'd be amazed how many companies operate their own mail servers, even behind dynamic addresses (in which case they usually use some mailbox polling mechanism to feed their server from mail from the outside), but send outgoing mail directly with SMTP.
Of course, one day we need a better protocol than SMTP (*Simple* Mail Transfer Protocol) which was never meant as a global email solution. But until then we have to do something to stop people abusing it.
But by killing the payload, not the messenger, please...
Cheers, Markus