Dear sir/madam,
[system: TiBook550 running OS 10.4.6. Mail 2]
When sending mail I sometimes get a message saying: "message could not be delivered ... verify that you have addressed correctly (which I have) ... Check you SMTP server settings and verify any advanced settings with your system administrator" I have repaired permissions (a habit which i believe is no longer neccessary) and even rebooted. My ISP is Eircom in Ireland
however, I have configured Mail exactly as per ISP's online instructions: Incoming/Outgoing as per ISP's website(POP & SMTP), Server port 25, not using SSL, advanced setting is port 110 not using SSL, authentication NTLM.
I share a DSL router with my landlord who is on a PC.
This sounds like a flakey configuration on your ISP's mail server.
NTLM is some Microsoft proprietary authentication protocol (what else need I say?). FYI, it appears that when you connect with your username, you must prepend the Windows domainname of the mail server to your username.
It is possible that OS X has some bugs/issues with NTLM, but you would have to open a ticket with Apple to resolve this.