I often come across data on what could be a relative, only to find it is not one I . Where do I record this information, so I do not research the same person again but keep it for if/when that person is found to be a person of interest?
This question is definitely not a duplicate! The question deals with the problem of recording the details about persons that we might be interested in, but before we know we are interested in him or her. I would suggest the OP edit the question to make this clear.
If the information is about a person, the easiest way to handle it with most current software is to simply create a new person record with only the new information and do not link that person record to any other existing persons or families. You will still be able to find that record when you search, so the information will not be lost. Later, when you learn enough to know who the person really is, you can either merge the record with an existing person record or just get rid of it.
This is getting precariously close to the whole topic of how do you transition from the "person-oriented" genealogy that we all do when we are beginners, to the "record-oriented" genealogy we must learn to embrace once we are dealing with generations way beyond living memory. Your question is really the very, very critical question of "how do I store my evidence before I really know what it means?"
I wanted to tell you to "create a new persona" for the information, but that's another topic that should be explored separately.
While I largely agree with Tom's response, I can think of situations where it may not be as black-and-white. I have certainly come across "interesting" information by accident that I didn't want to explore there-and-then because it might detract from the main topic I was researching.
In principle, creating a 'persona' (i.e. a separate person entity that is implied by that one-and-only source) would work but it could take a significant amount of time to construct it and add the appropriate details and citations.
Another possibility is to have a 'To Do' list and record informal details in there. In my case, this is just a text file into which I might paste a Web link, or search results, or even just a note to go and re-check something.
Depends on whether you are researching a particular person or gathering information on many individuals whose surname or location is relevant to your research.
In the first case, regardless of how the research of the "wrong" individual is recorded (as a separate persona, in research log notes, etc.), there should be a record in the original individual's profile that there is another person with similar details whose records have already been evaluated and been found not to apply - and the reasoning behind the conclusion. I use a custom event called "Other Relationships" where I can record that X is not the same as XX, and point to where the details are recorded.
In the second case, you probably would create working files, in whatever format(s) you prefer (database, spreadsheet, text file, even flow charts), to work through the original sources. Transfer to genealogy software with linkages between individuals could on a case-by-case basis or wholesale by source.