We know that Roddenberry often used to sidle up to actors he liked and tell them he was "writing a part just for you" in the next thing he was working on. I also heard stories - direct from Grace Lee Whitney - about when Landau and his wife, Barbara Bain, worked next door to the "Star Trek" soundstages, making "Mission: Impossible". They used to drop in all the time. They loved chatting with the cast and playing with the SF props. They actively sought science fiction roles for themselves and eventually succeeded in getting co-leads in "Space: 1999".
I am sure when Leonard Nimoy was making noise about whether to continue in Trek's third season, that Roddenberry tried to call his bluff. He reminded him that they already had molds of the ears of Mark Lenard and Lawrence Montaigne (both had played two Vulcanoids each already) and Martin Landau was ready to leap from "Mission: Impossible" if a SF project emerged. I am betting that this is when Laundau and Roddenberry had their discussion, if it happened.