I have finally found out why I have been having such epic problems with painting weights. The solution or should I say correct method was revealed to me while watching this video on painting weights.
Basically the guy in the video just runs through painting weights and discusses the key facts. He then spoke about the correct settings for adding weights to the joints. It is best to always use 'Add' and never to use 'Replace' because apparently when using 'Replace', influence is added to random parts of the mesh and screws everything up. As soon as he said that I knew it was the root of all the problems I have been having. So I went straight into maya and did a test, using Add is definitely the correct way and using replace does indeed cause the problems. So this has been the issue on my squirrel rig and the mother of all problems on my joe rig. I will now use this knowledge and paint effective weights onto the eel.