Have you tried cleaning the idle control valve?

^ yes gc8s can do a relearn

Ok well that clears that up,I have never done one on a gc8. As above take the intercooler off and go nuts with throttle body cleaner or carby cleaner

When you replaced the sensors, did you disconnect the battery for a couple of hours so the ECU re-set? If not, try that and see if it helps.

Also could be a crank angle sensor (CAS) problem. Have seen a couple of GC8's/Legacies with poor idle or no start from faulty (CAS). Sometimes unplugging and re-plugging the CAS was enough to get the car started or fix the idle problem for a short while. Once diagnosed, a new CAS fixed the problem.

[QUOTE=Avalanche;683860]Have you tried cleaning the idle control valve?
[/QUOTE]

I would try this first as you have already replaced the AFM etc.
I had a very similar problem with mine not too long ago, turned out the fuel pump was on the way out so on low loads is simply wasn't supplying enough fuel and then at high revs it was leaning out a bit too, so replacing this with a new Walbro/whatever unit might solve your issues, hopefully that helps mate ;)