I've just used ppm to install Net::DNS on winXP - no problem. Downloaded the source for Email::Valid as Valid.pm into directory C:\Perl\site\lib\Mail. Then tried a simple test of valid/invalid emails -worked.
Couldn't get a connection to use the 'check this is a valid host' test though probably I'm not set up correctly or firewall or something.
I think you have to run netlibcfg.pl in (c:\perl\bin or wherever.. ) to set up the connections.
HTH