Ok, looks like I was over-complicating matters. All I had to do was have a trace on one side and a trace on the other, and then strafe left or right depending on whether one was blocked. If they're both blocked then I just recalculate the path.
Seems to work just fine now, even for awkward passages like the doors in de_dust2
Just need better avoidance of other players now.