If you run dxdiag and see that you've got all the correct files, but you are missing registry keys try this:
Go to a command prompt:
type the following:
regsvr32 dpnet.dll
(dpnet.dll is directplay basically)
this should register directplay on your machine.
This worked for me on WinXP Pro, I know it'd work on NT, but I'm not too sure about previous windows versions.
If you've got corrupted registry keys, try the following from a command prompt:
regsvr32 /u dpnet.dll
regsvr32 dpnet.dll
(I think it's /u, it might be -u).
This will unregister the dll, and then reregister it.