Some very confusing traffic & comments here and a poor description of the problem.
Sorry but I cannot parse the meaning of "the server" when several servers are underdiscussion.
Here is what I *think* OP said.
The OP is running an SMTP server (call it OP-server) using dovecot & sendmail.
Dovecot is irrelevant as there are no complaints about the IMAP or POP3 service from OP-server.
He can generally send email from OP-server through some upstream SMTP server (call it UP-server).
When email is generated from some (local?) email client everything works as expected.
When email is generated from remote clients through OP-server, then UP-server reports an error
2nd problem - when a remote wandering (non-local IP) system attempts to send mail through
OP-server then the email (SMTP from the client) is rejected by OP-server(??).
I also want to point out that I believe that my server is directly talking to the servers of the recipients and not using my local ISP's server. And Dovecote on my server is excepting emails directly from the senders servers (or the senders ISP servers). I believe this because I never set up any email accounts with my ISP.
I'm fairly certain that you are wrong.
It sounds like you are running an open relay whether you know it or not. You had unauthenticated SMTP service accessible from the internet.
Dovecot provides POP3 & IMAP protocol which allows *clients* to read emails. It has absolutely nothing to do with mail delivery.
You are NOT directly delivering emails via SMTP to the destination. No serious relays or destinations accept SMTP connection from unregistered, unathenticated hosts b/c they do not want to become an open-relay.
When your upstream SMTP server states "Relaying denied", they are purposely preventing you from acting as a openrelay - at least for more than 1 hop.
You MUST use SMTP authentication - that should always be the case for any internet accessible SMTP server.
You *may* need to re-write the email headers to avoid the "Relay denied" from upstream. It's possiuble that the SMTP authentication alone will cause the headers to improve. Sendmail can do this, but you'll need a sendmail guru for help.