First, I had to install VC6. Since ActivePerl is compiled with VC6, compiled modules must use VC6's "cl" and "link". It places its command line utils into the PATH, so the system finds them. It's important to see nmake is there, it is used instead of "make" during the installation (perl makefile.pl ==> nmake ==> nmake test ==> nmake install).
It also failed to do linkage because "link" (did you know that 'which' works in windoze :-) was some oldish version on a network drive. Solution: (hear hear) disconnect the network drive, so it looked for it in a normal place (VC6's installation). I have a cleaner solution though - I'll play with the env vars via My Computer.
I still haven't been able to feed normal Windows paths to 'perl -MCPAN -eshell' though, to use minicpan's repository. But now, armed with success from the previous endeavor, I'm confident that I'll nmake it :-)