Many 3rd party email hosting providers are having to configure a 2nd port for their SMTP listeners. I don't know of any host that would simply let you relay through them though. If they do, let me know who they are so they get shut down 😀. One common port to use is 587, some other hosts use 2525.
I really don't mind that ISP's are doing this port 25 blocking... but for @$#% sake, notify your customers! I'm getting sick and tired of the 75% of support calls that are related to ISP's blocking port 25. Done ranting 😉