At this point I'm ready to do a low level format in order to try to get back the full capacity (since it looks like I'm in for a major re-build no matter what)
Keep away from the Low-Level-Format button ! There is no way for a user to low level format an IDE harddrive. Sending the command to an IDE harddrive might do unpredictable things to the HDD. Most modern drives just initialize their internal bad-block table (which happens very fast, that's why you think nothing happens) but older drives might even get destroyed completely.
What you are experiencing is a typical 4GB-Problem. You used a drive bigger than 4GB without installing the needed software patches. This leads to complete data loss sooner or later. That's what happened to you.
The 14MB printed by HDToolbox is not correct, either. Programs of that age cannot deal with numbers bigger than 2G. Therefore everything between 2G and 4G becomes negative and everything above 4GB becomes very small.
You have to calculate the correct numbers yourself. Or just trust HDToolbox that internally everything works correctly.
When creating partitions, make sure that the space occupied by all partitions together is smaller than 4GB. Do not create partitions on the right of the imaginary 4GB bar.
Bye,
Thomas