How to transfer an animation from a tree of empties onto an armature (space conversion)?
Now I got it! 



Bones are calculated using this code. Then the rotations are corrected locally, and finally the bones are rotated into the desired spot as if you rotated the whole skeleton in object mode and applied the rotation.

Overview:

#first create the matrices to correct the transformations
matrix_swap = mathutils.Euler((math.radians(90), 0, math.radians(90))).to_matrix().to_4x4()
rotateback = mathutils.Euler((math.radians(-90), math.radians(-90), 0)).to_matrix().to_4x4()

#create and pose the bone
bind = matrix_swap * bind * matrix_swap.inverted()
tail, roll = mat3_to_vec_roll(bind.to_3x3())
bone.head = bind.to_translation()
bone.tail = tail + bone.head
bone.roll = roll
bone.transform(rotateback)

#bring the keyframe into the right space
#we must make this matrix relative to the rest pose to conform with how blender bones work
key_matrix = fallback_matrix[bone_name].inverted() * key_matrix
key_matrix =  matrix_swap * key_matrix *matrix_swap.inverted()


The complete importer code is available on github.

Below is my original answer:



Not really an ideal solution, but at least progress.



This brings the keyframe from relative to the parent space into relative to the bone's own rest pose space:

key_mat = node_rest_mat.inverted() * key_mat


The keyframe would then work on the bone if the bone was oriented like the empty.

So I tried to orient the bones like the empties, ie. give them the same local orientation. I could not get it to work with the following 'reliable' bone creation code that I'd like to use:

 bone.head = mathutils.Vector((0,0,0))       
 bone.tail = mathutils.Vector((1,0,0))
 bone.transform(node_bind_matrix_worldspace)


Probably I was doing wrong matrix math with the bones... Instead I had to resort to this answer. I have used that in previous scripts but discarded it in favor of the above code, as manually calculating head, tail and roll tends to mess up the roll on some bones.

I will keep at it and see if I can do it with a nicely aligned skeleton...