I had the same trouble, looked everywhere for a php-mcrypt.dll to allow my php to use the m/crypt functionallity.
Alas I was looking in the wrong area, I found all the crypt tools I required in the latest snapshot of Pear (http://pear.php.net/), simply placed them in my php directory and it worked a treat.
Hope this helps you aswell.
Adios