Gidday I have a 1997 Legacy Lancaster Grand Wagon, and have exactly the same problem.
I dont even have to drive very far, or sometimes you just start it up in the morning and it cuts out after a few seconds.
Had a look at the wiring harness, the sensors, and still no go
Had the complete motor redone 2 months ago, both heads redone, new head gaskets, new gasket set on the entire motor, new water pump, new radiator, spent heaps on the motor, and still have the cutting out issue..
I love my suby, all of them, but this one is driving me up the wall