Ok, I had another Joomla install with the same host with this problem after receiving helo from Ordasoft. I didn't want to bother Ordasoft and have had reason to lose trust in my hosting provider the past few days, so I decided to check the settings for PHP again myself.

Problem is now fixed and uses the hash_hmac function as it should.

Turns out the php was php5.0; I changed it to 5.2 and it works beautifully.

So also check to see what version of php5 is being used on your server.

Thanks Ordasoft!