I'm thinking out loud here, but this is what I would do because I have found myself having to recompile php on many occasions.
1. Download mcrypt from source
2. Copy this tar ball to your /usr/local directory
3. exctract the tar ball tar -zxvof mcrypt.version.tar.gz
4. cd into the mcrypt directory
5. compile mcrypt make;make install
6. Create a softlink to mcrypt.v.3.blah by doing the following ln -s /usr/local/newcompiledmcryptversion mcrypt
7. Now you need to recompile your php, so take a peek at the config.log or config.status which contains the exact options you used to compile php which is found in your php directory, OR find out what php was compiled with by aking a phpinfo file. THis will tell you what you have compiled into php.
8. Get those options,and add --with-mcrypt=/usr/local/mcrypt
9. from php directory, do make;make install
This should get you going, but do keep an eye on things while you are compiling. Good luck!
Bones