Normal baking corrupted?
It's not really a fix, but I did manage to find a way around this.

Turns out when I generated normal maps that worked, I (accidentally) did it using Blender Render instead of Cycles.

So I moved my objects into a new file, did all my sculpting, and generated a half-decent normal map from them, which I can save and use in the original Cycles file with no issues apparently. There are still some weird bits but they're mostly parts of the mesh I didn't take much care with, as I won't be using the normal map for them. Getting the whole thing to a usable state would be pretty straightforward I imagine.

Result: