I have managed to use Mail::Mailer sucessfully on WinME, Win2k and on NT4. So it boils down to:

1. Where did you get the package from? Did you install the ActiveState version?
2. Are you using ActiveState Perl? If so you can grab the ppm version.
3. Have you installed it in a non-standard place. You'll need to "use lib" if so.
4. If it is in a non-standard place, where did you put it?

Also, can you post your test script so we can check that too?
Update:Someone further down this post mentioned that theres no archive from Activestate, well here it is.