Why do -Xmx and Runtime.maxMemory not agree

The difference appears to be accounted for by the size of the garbage collector's survivor space.

The -Xmx flag, as described in the docs, controls maximum size of the memory allocation pool. The heap portion of the memory allocation pool is divided into Eden, Survivor, and Tenured spaces. As described in this answer, there are two survivor regions, only one of which is available to hold live objects at any given point in time. So the total apparent space available for allocating objects, as reported by Runtime.maxMemory(), must subtract the size of one of the survivor spaces from the total heap memory pool.

You can use the MemoryMXBean and MemoryPoolMXBean classes to get a little more information about your memory allocation. Here's a simple program I wrote:

import java.lang.management.ManagementFactory;
import java.lang.management.MemoryMXBean;
import java.lang.management.MemoryPoolMXBean;

public class MemTest {
  static String mb (long s) {
    return String.format("%d (%.2f M)", s, (double)s / (1024 * 1024));
  }

  public static void main(String[] args) {
    System.out.println("Runtime max: " + mb(Runtime.getRuntime().maxMemory()));
    MemoryMXBean m = ManagementFactory.getMemoryMXBean();

    System.out.println("Non-heap: " + mb(m.getNonHeapMemoryUsage().getMax()));
    System.out.println("Heap: " + mb(m.getHeapMemoryUsage().getMax()));

    for (MemoryPoolMXBean mp : ManagementFactory.getMemoryPoolMXBeans()) {
      System.out.println("Pool: " + mp.getName() + 
                         " (type " + mp.getType() + ")" +
                         " = " + mb(mp.getUsage().getMax()));
    }
  }
}

The output of this on OpenJDK 7 for java -Xmx1024m MemTest is:

Runtime max: 1037959168 (989.88 M)
Non-heap: 224395264 (214.00 M)
Heap: 1037959168 (989.88 M)
Pool: Code Cache (type Non-heap memory) = 50331648 (48.00 M)
Pool: Eden Space (type Heap memory) = 286326784 (273.06 M)
Pool: Survivor Space (type Heap memory) = 35782656 (34.13 M)
Pool: Tenured Gen (type Heap memory) = 715849728 (682.69 M)
Pool: Perm Gen (type Non-heap memory) = 174063616 (166.00 M)

Note that Eden + 2*Survivor + Tenured = 1024M, which is exactly the amount of heap space requested on the command line. Much thanks to @Absurd-Mind for pointing this out.

The differences you observe between different JVMs are likely due to differing heuristics for selecting the default relative sizes of the various generations. As described in this article (applies to Java 6, wasn't able to find a more recent one), you can use the -XX:NewRatio and -XX:SurvivorRatio flags to explicitly control these settings. So, running the command:

java -Xmx1024m -XX:NewRatio=3 -XX:SurvivorRatio=6

You're telling the JVM that:

Young:Tenured = (Eden + 2*Survivor):Tenured = 1:3 = 256m:768m
Survivor:Eden = 1:6 = 32m:192m

So, with these parameters, the difference between the requested -Xmx value and the available memory reported by Runtime.maxMemory() should be 32m, which is verified using the above program. And now you should be able to accurately predict the available memory reported by Runtime for a given set of command-line arguments, which is all you ever really wanted, right?