If you're still working on this, try soaking the minis in acetone. This will strip off the paint, or at least damage it. But if the smoke is in the paint, and the minis aren't well painted, it should strip the paint off. Agitate from time to time by shaking. Don't leave for more than overnight if any of the base plastic is exposed.
The other thing you can try is TSP (Tri-Sodium Phosphate) which you should be able to find fairly cheaply at any hardware store. When I had to clean smoke from an apartment, it cut right through the staining on the paint. I just watched as the yellow gunk ran down the walls. Mix the TSP powder into water, wait a couple minutes, add your mini(s). Stir/shake every 10 minutes or so. Rinse off with clean water. If that doesn't work, go to acetone or consign to the dustbin.