Slight change of plan. Apparently mcrypt isn't a standard PHP module and I don't want to mess with requiring proprietary stuff. Instead of using AES, I'm just going to md5hash the password hash combined with the random string generated, do the same on the login server, and compare the two together.
I actually have this part working now. The problem is key generation time. In my test app, it takes less than a second to generate a key. When I put the code into paintball2, however, it took several seconds. I can't for the life of me figure out why, though. I hate to try to come up with yet another plan, though, when I've gotten this far. I might just have to put the login stuff in a separate thread and have it run in the background.