Sounds like it may be too late, or something else is wrong. If your car was running that rich for that long as to leave soot, I'm willing to bet your O2 sensors and catalytic convertor, have taken quite a beating. All those deposits must have seriously shortened the remaining life span of those O2 sensors and your cat. O2 sensors are pretty darn expensive, and oe cats are pretty bad on the wallet as well.

BTW, is the t-stat you bought from NAPA a fail-safe t-stat? The reason I ask is, the oe t-stat has a built in safety feature such that if and when it fails, it will fail in the open position, therefore allowing hot coolant to reach the rad and circulate. In the closed position, coolant will not circulate through the system. Your car can always be operated with the stat in full open position without doing any real damage, but too much driving on a closed t-stat in the right, or should I say wrong, driving conditions, will cause overheating VERY quickly, especially if you have a turbo.

Congratulations on tackling these problems.