I've had him at least three times in August and I don't TT. I've only had Saharah twice though and I've been playing since the start of July. I think it's just a matter of luck.
I had Redd in my town today. I got the statue with wings. I think one of the paintings was real, but it was a painting I already bought off of him so I didn't look closely.