Om du vill lösa det med port 25 så kan man alltid relaya mailen via ISP:ens mailserver.
Jag har kört en del med
http://www.qmailrocks.org/ och tycker det fungerar riktigt bra. Det är en bra guide, men titta igenom den och se om det är nått som behövs. Annars är det bara söka vidare =)