I've successfully created a C extension for Python, basically following the instructions given here. For the compilation, I used the free Visual C++ 2005 Express (internal version 8.0)
The exact steps I followed are:
Build Python from sources with MSVC 2005 Express, in both Debug and Release configurations. For this, go to the directory PCBuild in the source distribution and double click on the .sln file (Visual Studio will ask to convert it, since Python 2.5 was built on Windows with MSVC 2003). Select Debug and build solution. Then the same for Release.
Some libraries fail to build - this is normal. These are usually bindings to extra thing you have to install (Tk addons, bz compression, Berkley DB libs, etc). Python works fine without them.
Now, following the documentation instructions, I copied the \PC\example_nt directory, opened the solution contained in it, modified the Include and Linker Library directories path back to the source distribution, and built the solution.
example.pyd is created, and can be loaded and used by the Python interpreter.
Phew, this was much easier than I expected. It's another chance to appreciate the work that has been into Python to make it more friendly for Windows users.
Update: You don't even have to install the source distribution of Python to compile extensions. The binary distribution on Windows has the Include and libs/ directories that contain everything necessary to compile the extensions in Release mode. It is still recommended to have the source distribution handy, though, because it comes with a lot of examples and code from standard extensions to learn from, and you can use it to compile the extensions in Debug mode and run them with a Debug version of Python itself.