To sum things up, I am trying to use the "join as shapes" option, but for some reason the resulting shape key is really messed up. I made sure both meshes have the same number of vertices, and the toplogies seem to be similar enough, but am not sure why I am getting this result. Using transfer shape keys gets virtually the same result.
It's not about looking remotely the same, it's about being the same. You could add a cube to your scene, then add a plane and edit it to make an exact replica of the cube, chances are you will not have the same topology just because the Vertex indices will be different, and making a shapekey out of it will give strange results:
The normal way to do shapekeys is to either do them directly on the original objects itself (add a Basis shape, which is your original shape that you should never change, then make a new shape and edit that one), or duplicate your original object, modify the duplicate, and join that as shapekey to the original. In either cases, you should never add or remove anything from your mesh.
There might be a way to somehow recover your shape, I haven't tested that method though.
If they are visually strictly identical in topology but not in indices, maybe you can try to reassign the vertex order on both your original and shape object using this method, though it might break other things like UVs and weights, and it might still not work. I'm not sure.
Put the two objects in the exact same place, put your 3D cursor away from them using ⇧ Shift RMB, select both and switch to object mode before using the menu Mesh > Sort Elements > Cursor Distance. Then redo the shape key.