The best time to start an executive search for a key sales position is when there is a clear need for the role and the company has a solid understanding of the ideal candidate's qualifications and experience. It is important to allow enough time for a thorough search and selection process to ensure the right candidate is hired for the job.