DNS Reverse

Reverse DNS turns an IP address into a hostname -- for example, it might turn 192.0.2.25 into host.example.com.

dns-reverse

For your domains, standard DNS (turning a hostname into an IP address, such as turning host.example.com into 192.0.2.25) starts with the company (registrar) that you registered your domains with. You let them know what DNS servers are responsible for your domain names, and the registrar sends this information to the root servers (technically, the parent servers for your TLD). Then, anyone in the world can access your domains, and you can send them to any IP addresses you want. You have full control over your domains, and can send people to any IPs (whether or not you have control over those IPs, although you should have permission to send them to IPs that are not yours).

Reverse DNS uses a similar method. For your IPs, reverse DNS (turning 192.0.2.25 back into host.example.com) starts with your ISP (or whoever told you what your IP addresses are). You let them know what DNS servers are responsible for the reverse DNS entries for your IPs (or, they can enter the reverse DNS entries on their DNS servers), and your ISP gives this information out when their DNS servers get queried for your reverse DNS entries. Then, anyone in the world can look up the reverse DNS entries for your IPs, and you can return any hostnames you want (whether or not you have control over those domains, although you should have permission to point them to hostnames that are not on your domains).

So for both standard DNS and reverse DNS, there are two steps: [1] You need DNS servers, and [2] You need to tell the right company (your registrar for standard DNS lookups, or your ISP for reverse DNS lookups) where your DNS servers are located. Without Step 2, nobody will be able to reach your DNS servers.

If you can comprehend the above paragraphs (which takes some time), you'll understand the biggest problem that people have with reverse DNS entries. The biggest problem people have is that they have DNS servers that work fine with their domains (standard DNS), they add reverse DNS entries to those servers, and it doesn't work. If you understand the above paragraphs, you'll see the problem: If your ISP doesn't know that you have DNS servers to handle the reverse DNS for your IPs, they won't send that information to the root servers, and nobody will even get to your DNS servers for reverse DNS lookups.

Basic Concepts:

Reverse DNS turns 192.0.2.25 into host.example.com (an IP address into a host name).
Typical reverse DNS lookup path: DNS resolver => root servers => ARIN (North American IP registry) => Local ISP => Acme Inc. DNS servers.
Whoever supplies your IP addresses (usually your ISP) MUST either [1] set up your reverse DNS entries on their DNS servers, or [2] "delegate authority" for your reverse DNS entries to your DNS servers.
Reverse DNS entries use a host name with a reversed IP address with ".in-addr.arpa" added to it -- for example, "25.2.0.192.in-addr.arpa" (".ip6.arpa" is used for IPv6 reverse DNS lookups).
Reverse DNS entries are set up with PTR records (whereas standard DNS uses A records), which look like "25.2.0.192.in-addr.arpa. PTR host.example.com" (whereas standard DNS would look like "host.example.com. A 192.0.2.25").
All Internet hosts should have a reverse DNS entry (see RFC1912 section 2.1).
Mail servers with no reverse DNS will have a hard time getting mail to certain large ISPs.

Very Common Myth:

Myth: If you have a reverse DNS entry listed in your DNS server, you have reverse DNS properly set up.
Fact: This is often not the case. You need TWO things in order to have your DNS set up properly:

Your DNS servers (or your ISP's) MUST have the reverse DNS entries set up ("25.2.0.192.in-addr.arpa. PTR host.example.com").
AND your ISP or bandwidth provider MUST set up the reverse DNS on their end, so that DNS resolvers around the world will know that your DNS servers are the ones to go to when looking up the reverse DNS for your IP addresses.

How a reverse DNS lookup is accomplished:

The DNS resolver reverses the IP, and adds it to ".in-addr.arpa" (or ".ip6.arpa" for IPv6 lookups), turning 192.0.2.25 into 25.2.0.192.in-addr.arpa.
The DNS resolver then looks up the PTR record for 25.2.0.192.in-addr.arpa.

The DNS resolver asks the root servers for the PTR record for 25.2.0.192.in-addr.arpa.
The root servers refer the DNS resolver to the DNS servers in charge of the Class A range (192.in-addr.arpa, which covers all IPs that begin with 192).
In almost all cases, the root servers will refer the DNS resolver to a "RIR" ("Regional Internet Registry"). These are the organizations that allocate IPs. In general, ARIN handles North American IPs, APNIC handles Asian-Pacific IPs, and RIPE handles European IPs.
The DNS resolver will ask the ARIN DNS servers for the PTR record for 25.2.0.192.in-addr.arpa.
The ARIN DNS servers will refer the DNS resolver to the DNS servers of the organization that was originally given the IP range. These are usually the DNS servers of your ISP, or their bandwidth provider.
The DNS resolver will ask the ISP's DNS servers for the PTR record for 25.2.0.192.in-addr.arpa.
The ISP's DNS servers will refer the DNS resolver to the organization's DNS servers.
The DNS resolver will ask the organization's DNS servers for the PTR record for 25.2.0.192.in-addr.arpa.
The organization's DNS servers will respond with "host.example.com".