Ok, so after watching Crystal_'s video and then, looking through the code from GitHub and testing it for myself, I think I figured it out.
First, in crystal version, Kenji does not call for a rematch ever so, this is not a possibility to interfere with your PP UP collecting.
Second, he will not call you to let you know when you can come and collect a PP UP from him.
Whenever Kenji call you he will say:
"Hey (Player's Name)! This is Kenji!
Are you still on your journey? I remain dedicated to my training. Oooooaaarrrgh!
Anyway, we’ll chat again!"
Finally, you have to call him in order to find out when you can talk to him to get a PP UP. How does it work?
When calling Kenji, he has his greeting:
"Kenji here..."
and time-based response:
"(Player's Name)! Beautiful morning, hey?" During MORNING hours (4am-9:59:59am)
“(Player's Name)! Beautiful weather, hey?" During DAY hours (10am-5:59:59pm)
“(Player's Name)! Beautiful moonlight, hey?" *During NIGHT hours (6pm-3:59:59am)
and then... he has his 3 possible responses that are chosen randomly.
- "I apologize, but I don’t have time to chat while I am in training!
I’ll have time to chat tomorrow!
Yiiihah!"
- "I’m in training now. I apologize, but call me back another time.
Oooooaaarrrgh!"
- His lunch break response which differs depending on morning, day, and night.
• “I plan to take a lunch break, so come see me then! Ayiiiyah!” (Morning)
• “I’m taking a break on ROUTE 45! Why not drop by if you are free?” (Day)
• “I rested up over my lunch break. Now it’s time to resume training! Ooooryaah!” (Night)
and then he will give you his farewell:
"Anyway, we’ll chat again!"
Now the important part is the third part, response, this is where it is decided if he will have a break or not.
In my findings and testing, I found that I could not find him directly on break any day I called. I would only get the 1. response where he tells me he has time tomorrow. Now, this is because he cannot have a break unless he tells you "I can chat tomorrow" making the 3 responses the game has to choose from to be only 2 choices. Since the lunch break response can't be triggered w/o the prior "we can chat tomorrow", it will fail as a choice returning it as a "call back another time" response. This makes your chances of getting a "we will chat tomorrow" response a 1/3 chance.
So, you have a 1/3 chance to trigger his "we can chat tomorrow" response, which guarantees the following day to be a lunch break day. Now, on lunch break days, you can only collect the PP UP from him during DAY hours. If it is MORNING, he hasn't gotten to break yet. If it is NIGHT, you missed your chance for a PP UP and have to wait until the next time.
If anything is unclear and needs clarification, let me know and I will do my best! This is all assuming the code from GitHub is accurate and true to the original game and that I had found all relevant information to Kenji and this gift event in the code.
See RareCandyBar's Answer for a more complete answer.
Other source used for reference Bulbapedia