Line Trace Randomly Passes Through Actor

Usually I am able to fix bugs on my own by researching and testing but I have been stuck for 2+ weeks. Randomly (50%) the line trace will pass right through my NPC actors. I have tried sphere trace, cube trace, I have tried new blueprints, different meshes (in the video I use a cube!), all kinds of collision including block all, different maps (seems to only happen on larger open world maps) and a bunch of other things. I cannot find a solution.

In the video I have an AI actor using a behavior tree. It uses AI move to a random reachable place and then has a 2 second delay. It has a cube as a mesh with collision set to block all. But I have tried lots of other collision options and other meshes.