Ultimately, reverse engineering is the most comprehensive method, and it is certainly possible. There is also a dedicated Stack Exchange site for reverse engineering. Arguably, by trying out known passwords and checking the resulting hash values, you have already begun to reverse engineer that piece of binary software. There is nothing qualitatively special to decompilation -- what constitutes reverse engineering is the attempt at understanding, and you have made the first step along that path.
As for legality, it depends a lot on jurisdiction. What is traditionally said is that reverse engineering for interoperability purposes is fair game in Europe (as long as you just use, not publish, your findings) but maybe not in the USA. Laws on that subject tend to change fast, with things like the DMCA, so don't put too much trust in the reliability of the Tradition.
I suggest that you use the binary software to check the password for each user when that user logs in, but then, since you have the password available at that point, rehash it with another, secure and fully specified password-hashing function (say, bcrypt); that new hash will be used to verify further login attempts for that user.
That way, you may gradually move all password hashes to a new system, and after a while you will be able to decommission the old system with the binary piece of hashing. In any case, that old hashing is weak, since it is unsalted (an attacker who can look at the database will be able to speed up attacks a lot through parallelism), so you should build up a transition plan to a safer system.