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.
Maybe something in the the fabric of the universe just doesn't let people changed the past, making a new outcome, so J will be recruit one way or another.