To have emails sent out from a server and to pass certain validation tests you need to configure the server for SPF and DKIM.
SPF is a rather simple process that involves setting an SPF or TXT record in your DNS records. The receiving mail server, then checks the DNS record to see if the sending machine is authorized by your domain's records, just as you are describing in your question. A simplified explanation of SPF is that there is a record containing the IP addresses of the machines that are authentic mailers for the domain in question.
DKIM is a little more involved and may require you to configure a mail client on the sending machine.
From this page: http://www.elandsys.com/resources/mail/dkim/opendkim.html. Here's basically what DKIM does:
A domain owner generates a private/public key-pair that will be used to sign messages originating from that domain. The public-key is placed in DNS as a TXT record. The private-key is kept on the mail server which sends email for the domain.
When an email is submitted by an authorized user of that domain, dkim-milter uses the private-key to digitally sign the email associated with the sending domain. The DKIM-Signature header and signature is added to the email and the message is sent.
When a message is received with a DKIM-Signature header, opendkim extracts the signature and the sender's domain from the email. It does a DNS lookup on the TXT record to fetch the public-key for the sender's domain. Using the public-key, opendkim verifies whether the signature of the email is valid. An Authentication-Results: dkim=pass header is inserted as a mail header if the verification is successful.
I hope that points you in the right direction.