Different MD5 results

I strongly suspect that the hex conversion you're using in the application is failing if the leading nybble of a byte is 0. This is probably because you've got hex conversion code within the application itself, rather than using a standard library.

Solution: find the hex conversion code, rip it out, and use a standard library instead. For example, as it seems by your comment that it's the Java code which is producing the wrong result (your post isn't very clear) you could use Apache Commons Codec.

As noted in comments, however, it would be worth trying to avoid using MD5 anyway. That may or may not be feasible right now, but it should be on your medium-term roadmap.

EDIT: As a temporary measure, you could write your own PHP code to emulate the brokenness. Basically, you need to perform the normal MD5 hashing, then take the hex result and remove any '0' from it which occurs in an even position. So for example "ab0120" would end up as "ab120" - because the first '0' is in position 2, but the last '0' is in position 5. Alternatively, perform the hex conversion yourself, converting one byte at a time and trimming any leading '0' character from each two-character result. This code should be removed as quickly as possible, and only used to validate that users with broken stored MD5 hashes are valid.