I have found that the Clone Stamp tool is not very precise, and sometimes it takes multiple clicks to get it aligned exactly right. I'd guess it only gets the pixel I clicked maybe half the time, instead using an adjacent pixel as the clone source.
Below is a screen capture of it misbehaving. Notice it is a very small (20x10 pixel) image, zoomed to 5400%, so each black box is a single pixel. I have the Clone Stamp tool set to one pixel. In the below capture, I control click one black pixel, approximately in the middle, and then click another black pixel, also approximately in the middle, but it instead copies a white pixel adjacent to the one I originally clicked. This isn't just limited to small stamp sizes; I just did the 1-pixel size for this capture to make it very clear what is happening.
If I try again, I can usually get it to work within a couple attempts, even when clicking in approximately the same places, but it is inconsistent and annoying.