Big thanks for your detailed answers, they explain a lot. Also thanks for the link to the code. I will try to have a look into it though I am not sure if I will be able to do anything with it without frying my brain.
Now, I would like to further elaborate on the reason for the bugs. Though I guess you might have already thought about what I am going to say.
A lot of my creatures suffered from this bug but I also have a creature that seems to be immune to it. That immune creature is the one on wheels, let's call it "wheeler". What is the difference between wheeler and other creatures? When the wheeler "walks", its physical state eventually returns to the arrangement that it was initially in and it keeps periodically returning to that arrangement as it "walks". On the other hand the creatures that suffer from the bug have, at the start, a very unique physical arrangement that they never ever return to as they walk. That leads me to the conclusion that the bug must be hiding somewhere in the creation/initialization of creatures.
EDIT: So I downloaded the source, installed Unity, opened the project, pressed play, got notified of 58 errors, got headache :D
EDIT2: Managed to make it work! Hmm, when loading in my old creature it doesn't work as it was working before, is the source updated with some new code that makes old brains incompatible or something?
EDIT3: Ok, I noticed things are even weirder. I launch the game inside unity, load my evolved bipedal and it doesn't want to walk at all. I build an exe, load my bipedal with that exe and the creature walks as it should. I can't figure out what's going on.
EDIT4: As far as I understand the code "thinking" happens once per frame. Frames though are generated at different intervals as FPS is something that is constantly fluctuating. Maybe this causes different behaviours at different times and thus generates those bugs?
EDIT5: After changing some "Update"s to "FixedUpdate"s it seems like simulation got a bit more consistent but I am not 100% sure just yet.