The internet can't be built on certainties, so it's built on trust. Especially with the detection of spam, it's mainly a matter of trust - trusting the sending computer, trusting the sending domain, and trusting that the email in question really was sent by that domain.
Most anti-spam measures are aimed at one of those - for instance, SPF is all about demonstrating that the sending computer belongs to the sending domain, and DKIM is about matching the contents of the email
to its domain. The receiving MTA has to decide: Do I trust this sender enough to accept this email, or will I reject it? As an example, my own mail server checks a lot of things, including:
* How well the sender complies with the SMTP specification (if you can't get protocol right, I don't want to talk to you; if you deliberately violate protocol to try to conceal yourself, I definitely don't want to talk to you)
* Whether the hostname and IP address match
* Whether the reverse DNS for the IP address has four numbers in it (a common indication of home senders - c122-107-147-136.eburwd5.vic.optusnet.com.au looks like a home user); this doesn't prevent mail delivery, but it's marked down
* The SPF record for the sending domain, if it has one
* Certain source or destination addresses that have been blacklisted
* Bayesian similarity to emails previously marked as spam
* A few other details that I won't discuss in public, so you can't game the system and send me a pile of spam :)
Some of these checks are "below the waterline" requirements - for instance, if you don't say HELO or EHLO at the beginning of your SMTP request, I'm not going to accept any mail from you. Others are "above the waterline" - I'll still take the mail, but it's more likely to go in the junk folder, because I don't trust you that much.
Violating the internet's standards will often mean your mail gets rejected. There's a reason for that; trying to hide is usually a bad idea. Be honest; establish a domain and a (small) set of IP addresses that send its mail, and you can build up a record of trust ("Every message I've ever seen from foo.example.com (IP address 203.0.113.54 as per its SPF record) has been accepted by my users as legitimate, so I'm going to assume that this one, from the same domain and IP, is legit"). It's not even all that hard to do - just deploy one of the well-known mail servers like exim or Postfix, set up an SPF record (not actually necessary, but it's so easy and can help so much that I think everyone should do it), and let the rest take care of itself.
