1. How old is the battery?
If the battery is old, it will lose a lot of charge on startup. The alternator then starts pumping heaps of amps back to the battery to get it recharged. The ECU sees this amperage as some sort of error, and switches to a sort of limp mode that burns fuel like it was going out of fashion.
(the "O2 sensor" in the cat is the cat temperature sensor).
Have you had the injectors sonic cleaned?
Not "I ran injector cleaner", actually removed, cleaned and flowed in a sonic bath.
2. Try doing the HICAS diagnostic.
3. You have oil in the rear diff? Change the diff oil? (although it's probably shagged by now)