Carbon monoxide is harmless to an organism that has a way to deliver oxygen that doesn't involve binding it to something that is vulnerable to becoming tied up by carbon monoxide. I'm guessing nanomachines can do that, and moreover could be used to negate the effects of someone with carbon monoxide poisoning and normal blood. Someone who stores large amounts of oxygen in their body tissues, like a marine mammal, would also be resistant to carbon monoxide poisoning, since they'd have more time for it to leave their system before their oxygen levels became dangerously low.
For mercury poisoning and similar, I think it just comes down to 'do they have thingies that can remove this?'
Neither of these were examples of things that 'shred' organic molecules, though... that's just not how they work. And I can't think of anything that does anything like that aside from prions and enzymes and so on, which aren't really poisons. I don't know how to answer the question!