Went through exactly the same problem with emissions. My nox was 1100+. Pass in CA is 700ppm. Second time around my nox score was 500 something.
Did all the same things you did plus a decarbonizer-sludge remover called auto-rx (cause hubby had put stp in it to stop valve noise). I think of auto-rx as "seafoam for the faint of heart" (seaform is the product everyone was raving about that month but the stories scared me too much to go with a shock cleaning product). Read up on all the products people touted and in past threads and picked this one. It is about $25 by mail order only. I don't know that auto-rx is the reason for the big improvement cause I everything at more or less the same time. I would try it before replacing the cat.
http://www.auto-rx.com/
If you go this route, read the website carefully. If you do, there is a discount for reading the directions. LOL I of course, did not see that until after I had placed my order. By the way, the same product can be used for cleaning gunky transmissions.
Here is the link to the thread in which people gave me suggestions.
http://www.bimmer.info/forum/showthread.php?t=12713
You might also want to do the stomp test. Would give you clues about the cat and other possible problems. Stomp test didn't work for me but I have since read someothers can't get the stomp test to work for them unless they go through the steps about 5 times. Would give you clues about the cat and other possible problems.
http://www.bimmer.info/forum/showthr...ght=stomp+test
Dinan chip, Bilstein sports w H&R, RD sways, RD strut brace, 750 bushings, Zimmermans/MetalMasters, O.E. M Pars, Eisenmann muffler