I suspect that it's not staining that you see, but foreign stuff (fungus?) growing in the wood. Bleaching may kill it but it doesn't remove it. Kinda like powder post beetles - you can kill them but that doesn't fill the holes.
Routing and patching seems like a lot of work for a fix that will still be apparent. My feeling is to live with the 'stains' - gives the wood character. Rather like weeds in a lawn - gives it texture.