Go to the Slots tab of the tool shelf in texture paint mode.
Now there are two Painting Modes here Material, which I will talk about first, and Image.

When set to Material (as in the image above), all Image Texture nodes in the selected material are displayed as Available Paint Slots. All you have to do is choose the correct "slot" or texture, and paint.

Note that the Image Texture node does not have to be connected to anything, and it does not even have to be the active node anymore. (yeah!)
Now when the Painting Mode is set to Image, materials no longer matter, only the images. The image field under Canvas Image, is where you select what image to paint on. If you don't have on, there is a button to create a new one.

Having said all that, your problem is that you are no painting on the image you think you are.
Just the way you describe how it show up on other objects meas that, you are painting on an image that some other object is using.
Check the painting Slots as I explained above.