I had him on my very first day playing. He was going to Easter Island and I got the Moai statue. Which btw earned a bunch of points with HRA, so if he gives you something and you want high HRA points, display it in your home. Someone on my swapnote mentioned they believe he is timed (everyday at random times?) I'm not really sure if that is the case, or he just pops in time to time.