Grenage:
Real DNS lookups using forward and reverse DNS, assuming DNS caches are cleared.
Forward DNS, getting IP address of mail1.microsoft.com:
Using known address, ask h.gtld-servers.net for NS record for mail1.microsoft.com. Reply of a number of server names and IP addresses.
Send "A" query of mail1.microsoft.com at one of the provided IP addresses of a Microsoft name server. Get address.
Reverse DNS, getting name of IP address 131.107.3.125:
Send "PTR" query for 125.3.107.131.in-addr.arpa to h.name-servers.net using known IP address. Get reply of a number of DNS servers in the ARIN.net domain without IP addresses. Pick server name "dill.arin.net".
Send "NS" query for "arin.net" to h.gtld-servers.net. Get nameserver and IP address return.
Using provided nameserver IP address, send "A" query for "dill.arin.net" to nameserver. Get back IP address.
Using IP address of dill.arin.net, send "PTR" query for "125.3.107.131.in-addr.arpa" to server. Get back reply of "DNS1.CP.MSFT.net".
Send "A" query for "DNS1.CP.MSFT.net" to h.gtld-servers.net. Get back IP address.
Send "PTR" query for "125.3.107.131.in-addr.arpa" to IP address from previous step. Get reply of "mail1.microsoft.com".
Where a forward DNS lookup took 2 queries, a reverse DNS lookup to 6.
We get the two converse parts of a single question ("Are mail1.microsoft.com and 131.107.3.125 the same thing?"

for one of Microsoft's mail servers beause they have their own point of presence on the internet. If I were to perform the reverse DNS for the IP address of a legitimate, non-spamming bellsouth.net commercial DSL customer, chances are that the reverse DNS would not match the name provided by the customer's server. I'd get a reverse DNS report of something like "dsl-34.atlanta.foo.bellsouth.net", and it could take more DNS queries to get that answer.
Stevehewitt:
I'm not the one saying that legislation is unnecessary because there are techological solutions. If I can come up with an exploit that quickly, trust me, at least one spammer will come up with three in the same amount of time. Abuse of the internet mail system is, after all, their profession.
I've stated previously that there is no way to do without inventing a parallel set of protocols. I figure you're going to need some kind of server registry which provides tokens to all registered servers. Kinda like the SSL certificate signing authorities, who vet organizations to set up a hierarchy of trust. Then every mail server is going to provide in headers the token and a unique message ID.
You're also going to need a query protocol where an entity receiving a message can query the registry to insure the token has not been revoked, and can query a sending mail server to insure that it did, indeed, send the message, given a token an unique ID.
The registry is going to have to field reports from customers about receiving spam with valid tokens, so that they can make decisions about token revocations.
Of course, the registry is going to have to make enough money to pay all the people they have on staff to field spam reports and make decisions about revoking tokens. My ballpark figure is that they'll probably have to charge about 4 times what an SSL certificate signing costs per year: ~ US $600.
Of course, my idea isn't foolproof. A spammer can send out 10 million emails in a day, so all he'd have to do is get a token and send as many emails as he can before the token is revoked. And all this extra infrastructure does not give you a way to tell whether an email is spam. It just sets up a hierarchy of trust as to the intentions of the sender.
So we get back to my original thesis that legislation is a necessary part of the solution. Let each country make it illegal to send spam and have consistent rules as to what constitutes spam. If someone anywhere spams, then let his local judiciary deal with him.
Want the best answers? Ask the best questions: TANSTAAFL!!