It's when you beat the Pokémon League.
He doesn't "sometimes" appear, he appears one time then leaves when you talk to him.
Once you've beaten the Pokémon league, he is guaranteed to appear in B1 of the Veilstone Department Store.
After you encounter him, though, he will disappear permanently.
That's.... Anticlimactic. Okay, I'll give you really specific information I figured out:
- He stays there until you talk to him.
- He disappears when you leave the room (not the building).
- If you see him, talk to him, save in front of him, and reset before leaving, he will not disappear yet and will remember that he already talked to you once (he skips his lines about Rage Candy).
Rechallenging the Pokémon League will not make him reappear.
And in case you were wondering, he still shows up in his lab even while he's set to appear in the department store. Visiting his lab does not interfere with this event.
SO happy I wasted my time on this.