I actually had queue_free() in the code at first, but it removed the node 'too late'.
The intended functionality was:
First child of a node is queue_free()'d
New node is instanced and added as child (replacing the above)
Method is called on new node
However, what actually happens is:
Method gets called on the first node, probably because it hasn't been freed yet
I randomly changed it to free() which made it work fine so I kept going (only for free() to cause the 'locked' issue later when i added a different type of node that goes through the same process.)
In hindsight, there isn't actually any need for the node to be freed instantly. Like you say, just using remove_child() to 'get it out of the way' when needed, and having queue_free() clean it up later, would be way better.
I am still curious about when a node is 'locked' though, as the node that had that issue really did not seem like it would be executing anything when free() was called on it.