I want to remove those edges along with their vertexes but It only deletes the edges and some of the vertexes then selects seemingly random edges afterwards. This has never happened, I have deleted by history and restarted numerous times.
Is there any history on the mesh other than the stuff required for animation? If so, try an edit>delete by type>non deformer history. I doubt that's the problem, but it's worth a shot.
Sounds like a fluke. Have you tried selecting all the verts and welding? Delete history? Or try combining the model with a cube, then delete the faces for the cube, then delete history.
probably soemthing in the history of your mesh. ;) if you have your old file, select the mesh and go to the attribute editor. there are numerous tabs there, some of them history nodes. my guess is, some of them might clash with your edits. i always try to delete history before i bind a mesh...