שלום
הר״ן כתב יסוד גדול, והוא דאיסור לא תנחשו הוא שתולה את דבריו בסימן שאין הסברא נותנת שיהא בהם תועלת לדבר או נזק, כגון פתו נפל מידו וצבי הפסיק לו בדרך, אבל הלוקח סימנים בדבר שהסברא נודעת שהן מורים תועלת הדבר או נזקו אין זה נחש, שכל עסקי העולם כך הם שהרי האומר שאם ירדו גשמים לא אצא לדרך ואם לאו אצא לדרך אין זה נחש אלא מנהגו של עולם.
ובזה מבאר את שעשה אליעזר עבד אברהם [שאמר הנערה אשר אומר אליה הטי נא כדך וגו' אותה הוכחת לאדוני ליצחק] ויונתן בן שאול [(שמואל א פרק יד – י) וְאִם כֹּה יֹאמְרוּ עֲלוּ עָלֵינוּ וְעָלִינוּ כִּי נְתָנָם ה' בְּיָדֵנוּ וְזֶה לָּנוּ הָאוֹת וגו'] בדוגמאות מעין אלו תלו מעשיהם, שאליעזר ידע שיצחק ישא אשה ההוגנת לו וזה הסימן שלקח שיראה שהיא שלימה במידותיה, וכן יונתן בן שאול, שהיו הוא ונושא כליו בלבד, לקח הסימן לעצמו
שאם יאמרו "עלו אלינו" היינו שהם יראים ממארב ובזה סמך על גבורתו שהוא ונושא כליו יפגעו בהם, ואם יאמרו "דומו עד הגיענו אליכם" היינו שאינם מפחדים, לא יכניס את עצמו לסכנה.
נמצא איפוא לדברי הר"ן שהאיסור הוא רק אם סומכים על הניחוש, ובדבר שאינו מסתבר ואין קשר הגיוני בינו לתוצאה. אך אם אינו סומך על הניחוש והוא רק כסימן, ויש קשר הגיוני בינו לתוצאה – אין זה ניחוש. ומעי"ז במהרש"א [חולין צה:] שכתב שניחוש נקרא רק אם אומר את ב' הצדדים, כדוגמת יונתן וגם רק אם סומך על זה.

בנוגע לשאלתך על גדולי ישראל שלא פעלו בענין מסוים לאחר ג' פעמים שלא הצליחו, זה אינו דומה כלל לניחוש, ששם הטעם הוא משום ריבוי ההשתדלות במקום שמשמים מונעים אותך – שזה הוא דבר פגום ומבטא חוסר אמונה, ולכן ראו בכך רמז לחדול.
לסיכום – קולמוסים רבים נשתברו בנושא זה איסור ניחוש, ואוכל להפנות אותך למאמר של הרב דוד ולנשטיין [קונטרס 'אוצרות ירושלים' כרך יא עמ' שעה], ולספר אמרי יושר [(גריינימן) חולין צ"ה: עמ' סט] שהאריכו בשיטות שנאמרו בענין.