[ToyotaDon]

O2 sensor won't have any effect when cold, its signal is ignored.

Are you sure the rebuild is 100%? It wouldn't hurt to run a compression check to be positive.

High NoX can also indicate a lean condition, not necessarily a vacuum leak, but something else that could cause it to run lean. Do you know anyone with a scanner who could look at the datastream for anything out of the ordinary?