There's going to be a degree of soot, but when it looks like the walls of a fireplace it is a clear indication that your running rich = unburnt fuel. As there is nothing visible on your paint then it is not horribly bad because that is when it really shows. Was your other paint job covered in soot?

Aside from the honda top end cleaner, people have also tried Seafoam which is less expensive. This will clean the motor out, so in case you have a heavy carbon build up, which could hinder fire power, that will eliminate most of that. The car will smoke like a bitch and that means it is working so don't shit yourself. After about 3 minutes of smoking your neighbors should be pretty pissed so go for a drive and blow that shit out. You may notice an increase in power as well, this does not mean you gained HP per se but that you have revived hp lost. so glass 1/2 empty or 1/2 full what have you.

If the backfire is still there move onto the other factors. Take note of the frequency of the backfire though. It is a process of elimination. Start w/the most affordable things first.