Hey LuxXeon, Yes, I have been struggling with blender in that it doesn't seem to allow Keyframing and NLA strips at the same time. I seemed to make progress in "editing " the NLA clips and re keyframing the existing clips to make new NLA strips. So, what you say very well could be true that it is a problem with the NLA strips. somewhere.
I think you have to disable all NLA strips then you can Keyframe a new animation , save out the new animation to a new NLA strip, turn on all the NLA strips in the NLA editor then add your new NLA clip.