After some in-depth analysis, I determined the following:

1) The new symlink-aware os.stat has to find the target of a symlink to
properly function.
2) The previously-proposed patch uses GetFilenameByHandle in os.stat to
find the target, but this fails when a handle can't be obtained (such as
when a symlink points to pagefile.sys.
3) Explorer doesn't use GetFilenameByHandle. I used ProcMon to monitor
the API calls when it looks up the properties for a symlink to
pagefile.sys. It appears to use CreateFile and DeviceIoControl to trace
through the symlink chain.

So, I've written a proof of concept that determines a symlink target
using these API calls. The code is in jaraco.windows.filesystem at
https://svn.jaraco.com/jaraco/python/jaraco.windows/jaraco/windows/filesystem.py:trace_symlink_target
.  For convenience, I've pasted the most relevant code segments at
http://paste.turbogears.org/paste/122986 .

I'd like to get comments on this implementation before porting this to
the C code and adding it to the os.stat call. One of the aspects that
makes me uncomfortable is the fact that I have to call relpath between
each iteration.

I have tested this approach fairly thoroughly. It appears to work under
all circumstances (through multiple symlinks across drives and
ultimately pointing at pagefile.sys).

If no one can suggest a better approach, I plan to code this into the patch.