Sending Email


I was using the client "Mail" on a Mac G4 10.28 to send and receive emails for a couple months with no problem. All of a sudden I was unable to send or receive emails with an error message stating something to this fashion:

"The outgoing mail server "" failed to deliver this message. The server "" can not be contacted on port 25."

The account information was never changed (previously). I've tried:
-changing account settings
-using "Microsoft Entourage" (similar error message received)
-Using other email accounts
-switching internet access at different locations

I know the email accounts work on other computers with the exact same settings. Now once in a while a message will be sent out succesfully on a first try after starting a new session but then will not work again even with re boots.

This has been very frustrating, can someone please advised to a posible fix, any advise would be more then appriciated. Thank you