Your problem is relative to empties rotation.
Position of child is relative to position and rotation of parent.

Problem is more obvious if parents have not the same rotation.

You can avoïd this simply by disabling influence of parent rotation.

Disabling the influence of parent rotation is not an option. The object would be facing the wrong direction (which is pretty obvious when you use something other than the default cube or rotate by 45d instead of 90d).

As for the .blend file, I see actions for Comment, Change Status, and many others, but no Upload File. And there is no way for me to drag&drop files. I uploaded it to pastebin until the web site is upgraded:

http://www.pasteall.org/blend/33696

Questions that remain:

• What is the mathematical reason for the oddity in the calculation?
• Is this existing mathematical model superior for any applications?
• Is there another model that would give less surprising results in this case and in the majority of other use cases?
• What would break if the mathematical model were altered to give less surprising results in this case?
• Is it worth the effort to alter the code to implement a "better" model?

When influence of child of constraint is decreasing, it is like cube was moving far away from empty location.

In this .blend, you can disable rotation influence of constraint and see the cube static.
If you keep z rotation active and disable all location influence, cube is just rotating on its own axis.

It is combined influence that produce same result than in a child-parent relationship.

Tipically child of constraint is used to attach an object on a different parent in an instant with a contact.
I have an object in the hand. I put it on the floor. Another character pick it.
It is not supposed to be used to make an object flying from my hand to the hand of the other character.

If you want to create translation and with constrained rotation, use "copy location" and "copy rotation" constraints.

After some experimentation I have developed the theory that it's because multiple child-of constraints with fractional influence are implemented by creating a transform matrix for each constraint based on the difference between the decomposed loc/rot/scale of the two parents, and attenuated by the influence.

Once these matrices are chained together, things get a little weird.

I was able to achieve the effect I wanted by separating the location/rotation constraints with the location constraints at the top of the stack and rotation at the bottom.

I'm going to vote we file this in the "undocumented oddity" bin.