OK, just to set things straight:
One: there is no apparent danger from the malfunctions I'm describing. As Ldots indicated, the tools always generate the same password for a given drive, so no problem. If I accidentally lock with the wrong one, I can always run the unlock command to use the same (wrong) password.
Two: I would like to emphasize that I can see the plain-text, presumed correct (since LiveInfo generated the correct PW for both of my hard drives using it) HD key in the hd text files generated by both CM and Evox, and that when I run the linux tools to examine the eeprom.bin file created by either of those apps, they display the HD Key (supposedly from the eeprom.bin file) and it does not match. So, the generation algorithms are probably fine, and I think it's reading the serial numbers correctly in all cases as well (so not an issue with my PC BIOS).
The heart of the issue is that LiveInfo can read the eeprom.bin files correctly, and xinfo (for instance) cannot. I'm pretty sure that if I had a linux tool that I could pass a hand-typed HD key to and have it spit out a password, that would work fine. It is only the part where the HD key is extracted from the eeprom.bin file that seems to be broken. The one thing I have not checked is whether every time I try to read the eeprom.bin under linux, it gives the same (wrong) value.
I have tried it on two completely different computers and have the same problem for each. I'd be interested to know if anybody else with the exact same xbox as mine (see my sig) has gotten this to work.
I will try downloading the UDE installer later tonight, or tomorrow. If I get any different results, I'll let you know. This thing has been driving me crazy, and I'd hate to put anybody else through what I've had to deal with.