In the Men In Black 3 movie, the timeline was altered after K was killed in 1969. In the new timeline, K wasn't alive to recruit J. So, how did everyone (O, etc.) recognise J?
I was thinking about this myself and I came up with a reasonable answer:
Since young J was neuralized and K (presumably) merely kept watch over him for the rest of his life, not interfering with it, in the original timeline, it stands to reason that a J that was never in contact with K would have the same attributes and personality that made him a good agent in the first place. So, even without K's influence, he could have been recruited by another agent simply because he was MIB material.
Yeah, I know it's not a great addition to the story, which is probably why they didn't address it. It doesn't really leave a gaping plot hole either.
My theory is a little different.
We know that Griff was with K at the time in the timeline Boris made, (and in all others in fact) and he showed something to J's father, in order to convince him to let them pass to deploy the arcnet.
After K's death J's father could had been recruited my MIB since he was MIB material as noted by K in the "correct" timeline, and most likely that J's father recruited his own son and explaining his absence during J's childhood and everything.
O knows J is from the future in 1969, she could have put him on a watch list to recruit him in real time. Or J's dad could have been recruited (hence the lack of J having a father growing up) and either h or O recruited him without telling J that his father was in the organization.