Historically, SMTP connections to port 25/TCP were used by both email clients (MUAs) to send outgoing mail to their local mail server, or by mail servers (MTAs) to pass email from one mail server to another. No authentication was included as standard. This turned out to be a very bad idea.
To fix the problems caused by this, modern mail servers are usually set up to accept incoming email from clients using port 587. When using this port, authentication is usually mandatory, and TLS encryption (using STARTTLS) is highly recommended.
The port 25 is increasingly dedicated to traffic between "valid" mail servers only, and the validity of a particular mail server is mostly decided by various DNS records.
"Relay access denied" means that you're not currently authorized to send email through the external server to any other mail server, i.e. mail relaying like
YOURSERVER -> EXTERNALSERVER -> THIRD-PARTY-SERVER
will be blocked. If the destination address of the email you're sending matches one of the domains EXTERNALSERVER is directly responsible for, it should still be accepted, unless you're failing other anti-spam checks.
There is a number of various anti-spam tests that other mail servers may apply to an incoming SMTP connection:
On connection, the connecting host needs to state the hostname it claims to be. The receiving host will perform a reverse DNS lookup for the source IP address: does the name reported by DNS match the name claimed by the connecting host? A regular forward DNS lookup is also performed: does the IP address reported by DNS for that name match the source IP address the connection is actually coming from? This is one of the oldest anti-spam tests. If you fail this test and don't authenticate, you'll be allowed to only send email to the email addresses the destination host is directly responsible for, not to any third parties.
There are also DNS SPF records which can (optionally) specify which hosts in a particular DNS domain are supposed to send email to the internet. If your domain has a SPF record (try
dig domain.name TXT to see) and that record indicates your host is not supposed to be a mail server, and you're not authenticating, the external server may reject your connection attempt completely.
DNS MX records are another important part of email delivery: they specify the actual hostname of the mail server(s) serving a particular domain. In order to determine where email addressed to
Joe.User@domain.example should be delivered to, email servers will first look up a MX record for
domain.example. You can do it yourself with a command like
dig domain.example MX.
If there are no MX records for a particular DNS domain, there is a fall-back rule: if there is a plain old DNS A record for
domain.example and the host in the IP address identified by that A record listens on port 25/TCP, then any emails addressed to that domain will be sent to that IP address.
For anti-spam checks, the MX record of the sending host may be checked: the idea is "if you don't look like you're prepared to receive email, you probably should not be sending it either." Because of a large variety of mail server set-ups, this cannot be a hard and fast rule, but it is occasionally used as a small positive/negative factor in the "spam or not?" decisions.
If you are a home user or even a small business, without a static public IP address, an internet service provider may choose to treat you as a simple email client, and only allow you to send outgoing SMTP connections to the provider's email servers only. They may require authentication at that point, or they may allow unauthenticated connection based on the physical structure of their network. In this situation, you can still have your own private mail server; it just needs to send all outgoing email through the provider's mail servers just like a regular email client would. This is sometimes called a "smarthost" configuration, according to the name of the configuration option for it in the classic Sendmail. In modern times, using port 587 and authentication instead of classic unauthenticated port 25 is usually required.
Receiving incoming email in your own server also depends on what is allowed by your internet provider. If your connection is NATted (as home and small-business internet connections increasingly are), receiving incoming connections without opening a fixed tunnel for port 25 through the NAT will be impossible. If your IP address occasionally changes, keeping the email-relevant DNS records always up to date will be critical for the reliability of your email delivery.
Once you have a public static IP address and a DNS domain of your own, you are generally considered "big enough" to have a "real" mail server in the eyes of the internet at large. When setting up a mail server, you should pay very close attention to various types of DNS records relevant for email delivery, and make sure that your server introduces itself (the HELO/EHLO message in the SNMP connections) using the exact name registered for it in the DNS. Also make sure that the reverse DNS record (PTR record, for the IP address -> domain name mapping) is correct.