Heh, cheers Drue, your a legend, but I just figured that out and was coming back to post the solution. I (and I'm guessing chrissanz and the others with the same problem on Google) was installing it like an extension and not like a library.
I was trying to use:
extension=libmcrypt.dll
in php.ini
I even renamed it at one stage to mycrypt.dll because I though that that's what the readme was saying. My problem was the extra 'y'. If I had realised that it was 'mcrypt' and not 'mycrypt' I would have spotted the dll and the reference in php.ini and would have worked things out faster.
BTW, for anybody else with the same problem, you just need to add the libmcrypt to any folder that is a system path. For me, once I realised my error, I just added it to my root PHP directory, uncommented the ;extension=php_mcrypt.dll line in php.ini and restarted the server and everything worked.
So pretty much the same process that Drew described.
Cheers again Drew, you were about 5 micro seconds late to help me with my stupidity, but I'm sure the next sucker will be along via a Google search any time soon. =D