Traced the problem down to the following minimal code snippet:

import marshal
s = 'c' + ('X' * 4*4) + '{' * 2**20
marshal.loads(s)

When Python/marshal.c:18 MAX_MARSHAL_STACK_DEPTH is 2000 (which is what
it is currently), marshal.loads() eventually overflows the stack in
r_object().  There is a check in r_object() to avoid this though:

  if (p->depth > MAX_MARSHAL_STACK_DEPTH) {
      p->depth--;
      PyErr_SetString(PyExc_ValueError, "recursion limit exceeded");
      return NULL;
  }

On Windows x64, a value of 1964 raises the recursion limit exception
above (which is what test_marshal is expecting).  With a value of 1965,
a C stack overflow exception is raised.

So, MAX_MARSHAL_STACK_DEPTH needs to be <= 1964 in order to prevent this
particular code from overflowing the stack on Win64 before we can raise
a Python recursion limit exception.

Was there any science behind choosing 2000 as the current value?  Should
a new value (e.g. 1500) be provided for only Win64, leaving everyone
else at 2000?  Interesting that Linux/BSD etc on AMD64 don't run into this.