For future reference and in case anyone else runs into the same kinds of problems, here is what I ended up doing.
The situation is I have an AudioProcessorGraph inside my plugin which I use to allow the user to freely connect some modules. The modules are now implemented as AudioProcessors and have the ability to fade in and out of processing so they can be added and removed to the graph without cracks and pops. There is a data-pump thread that removes no longer used modules once they declare they are done fading out.
I use the AudioProcessorGraph as an independent object and initially I forgot to use the callback lock during processing which resulted in lots of bad crashes. But the crashes didn’t fully stop once I used that and I found out the problem is my data pump thread which removes nodes and connections and sometimes creates shortcut connections.
I got issues because the graph updates using the AsyncUpdater class which means the updates run on the juce message thread. If an update collided with my data pump thread undefined things did happen.
I ended up copying the whole source of AudioProcessorGraph to create my own version. In my version I added two critical sections, one for the nodes array and one for the connections array and now these arrays are protected during iteration at all times. I later removed the AsyncUpdater altogether because I heard about problems with the message thread in this forum and now I’m using my data pump thread to do the updates as well which probably means the critical sections don’t ever block.
I also added stuff to my altered class to postpone updates during patch restores where lots of graph chances lead to multiple graph rebuilds in a row.
I haven’t seen a crash in days with these changes.
I think it would be nice to add a sentence to the AudioProcessorGraph description about thread safety of the class. Which is more or less non-existent. As previously stated I believe it only works correctly as long as all graph manipulations come from the message thread which is unfortunate for my use case and is also not at all visible anywhere in the documentation.