Clare, I think we've resolved this via email, but for the benefit of others who may be reading along here, I'll paste the explanation and advice I gave you:
It's really a fairly simple process, and there's always a clear reason why a given file upload would fail to get prepped for stamping. If a new upload gets properly prepped for stamping, that file should then get stamped for every checkout, but if it fails to get prepped in the first place, then it will never get stamped.
If you have a known-working file uploaded that gets stamped reliably, and then you replace that by uploading a new file, that introduces a chance that the new file may inadvertently have the wrong settings which would cause it to fail to get prepped for stamping properly -- e.g., password locked with Acrobat 7.x compatibility rather than 5.x or lower, or password-locked when you meant to upload an unlocked original, etc.
If you're going to be updating your original file frequently and want to streamline that procedure for stamping reliability, I would suggest if you always upload originals without an authoring password (in which case the compatibility level should not matter), which would become locked with a random authoring password in due course of stamping anyway, and then do a test checkout 15+ minutes after every new upload to verify you receive a stamped copy of the file (which indicates the new upload got prepped properly), that should be a reliable solution.