@Zach - thanks for the review. Sorry that it has taken a few months to pick this issue back up. Anyway, here is an updated patch. It is pretty different than the previous patch, to the point that I would consider it a completely new patch.
Anyway, here's a basic rundown of what the patch contains:
Two functions in Modules/posixmodule.c were modified to handle bytes objects as well as str objects: win_readlink and _getfinalpathname. This was necessary to allow os.path.realpath() to continue returning bytes when supplied with bytes. I know you said in your review that you didn't care about this because using bytes paths on Windows is deprecated, but I think it still important to maintain backwards compatibility.
A new implementation of realpath() was added to Lib\ntpath.py, used when _getfinalpathname is available (when _getfinalpathname is not available, realpath remains a synonym for abspath, as it was previously). The logic here has been completely reworked and is roughly modeled on the realpath implementation from Lib\posixpath.py.
A number of tests were added to Lib\test\test_ntpath.py for realpath() functionality. Three of the tests were based on realpath() tests from test_posixpath.py, but one is completely new: test_realpath_broken_symlinks.
A note about improved Windows support was added to the documentation for realpath(), but no other doc changes have been made.
Anyway, feedback is welcome - I'd love to get this code in sufficient shape to see a working realpath() implementation for Windows land in Python.