threading.Timer gets cancelled but doesn't stop firing. Why?
I found it before I got to post the question, so instead of discarding it I will post the response myself.

The problem was that (coming from javascript and jquery) I was expecting Timer.start() to return the timer object, but it just returned None so cancelling it had no effect.

The working code is as:

def execute(op, context):
    print(op.stop)
    if context.scene.animall_timer.timer is not None: context.scene.animall_timer.timer.cancel()
    if not op.stop:
        context.scene.animall_timer.timer = threading.Timer(op.time, op.execute, [context])
        context.scene.animall_timer.timer.start()
        context.scene.frame_set(context.scene.frame_current + op.frames)
        bpy.ops.anim.insert_keyframe_animall()
    return {'FINISHED'}