From the ActiveState, Perl, Download, MSI link did you:

1) Review and meet the Windows System Requirements?
2) Have a recent install of InstMsi.exe (linked from there)
3) Make sure your NT Server 4.0 has SP5 or later applied?
4) You must uninstall all previous Perl versions from Settings, Control Panel, Add/Remove Programs first
5) I'd also suggest deleteing the c:\Perl (or whereever) directory from Explorer by hand as well before reinstalling.
6) During install select "create file associations" and the other three check boxes (to integrate with IIS) properly

I just install that very release yesterday on my NT 4.0 (SP6) Server and it worked just fine!