The word you're looking for is
justified, as in "
knowledge is justified true belief." The consensus is that justified true belief is at least a necessary condition for knowledge, though not sufficient.
There are many types of justification out there, I guess. But even the weakest justification can resolve your apparent paradoxes. Mary can propose "since when has Rebecca pulled a trick like that with the birthday party?" to get John to think differently. We know a red ball exists either by holding it and thinking that sensation of a round thing in our hand justifies the thought, or get someone else to confirm there's a red ball there, among other things. When your thought experiments seem counterintuitive, it's probably a sign that it isn't attacking something as fundamental as you may think.