changing the port between 25 and 587 will work when you ISP has blocked port 25. Some ISPs are doing this in an attempt to help burb spam - they think that if you send all outgoing E-mail through them they can monitor it and block more spam.
So this would be a logical fix it was a consistant 'I can never send outgoing E-mail any more'. However, as it's not, it's more likely to be an issue with your mail server. I know my mail server has a similar problem once in a while - I'll try and send an E-mail and I'll get a relay access error. Send it agian in 30 sec and it goes through just fine.
I would sigguest you put a ticket into support, explain the nature of the on again, off agian problem, how often it occurs, and any other information that may be helpful. Perhaps someone else who uses the same server as you will have allready reported similar problems and they'll be able to match then up and fix the problem. It's worth a try anyways.