מסקנות הוועדה הובילו למבוי סתום. לבון, אשר טען שקציני צה"ל עשו יד אחת בוועדה כדי להפלילו, דרש מראש הממשלה שרת את פיטורי ראש אמ"ן, בנימין גיבלי, ומנכ"ל משרד הביטחון, שמעון פרס, כתנאי להישארותו בתפקיד שר הביטחון. שרת, אשר אמנם קיבל את מסקנת התיקו של הוועדה, עדיין ראה בלבון הגורם לפרשה, גם אם לא הגורם הישיר לה, סירב לערוך כל חילופי-גברי בצבא ובמשרד הביטחון, כדי שלא יתפרש כלפי חוץ כהודאה של מדינת ישראל באחריותה למעשים במצרים, ובעצה אחת עם השרים גולדה מאיר, לוי אשכול וזלמן ארן דרש מלבון להישאר בתפקידו זמן מה ללא תנאים. שרת כתב על כך ביומנו:
סיבה נוספת לדרישה שלבון יישאר בתפקידו הייתה שלא נמצא אדם מתאים להחליפו בתפקיד. שרת, שכבר כיהן כשר החוץ בנוסף לתפקידו כראש הממשלה, לא חשב שיוכל להקדיש זמן מספיק לתפקיד, וכך גם אשכול שכיהן כשר האוצר. התפקיד הוצע לסגן שר הביטחון לשעבר שאול אביגור, גיסו של משה שרת, ולרמטכ"ל לשעבר, יעקב דורי, אך שניהם סירבו. במהלך התקופה הוצע התפקיד על ידי מתווכים כיצחק נבון ונחמיה ארגוב לראש הממשלה ושר הביטחון לשעבר, דוד בן-גוריון, במקום מושבו בשדה בוקר, וב־17 בפברואר הוא הסכים למינוי. באותו יום מסר פנחס לבון את התפטרותו, כאשר הסיבה הרשמית להתפטרותו הייתה "בשל תביעות שונות מצד לבון לשינויים שונים במערכת הביטחון אשר לא נתקבלו על ידי שרת".
המשורר נתן אלתרמן כתב שיר על הנושא, שהודפס ב"טור השביעי" בעיתון "דבר" ב-11 בפברואר 1955, לאחר שאושר לפרסום על ידי הצנזורה. המשורר שואל "אם היה זה ראוי ונחוץ" ו"אם אמנם עלינו ליתן את הדין על מידת קלות־יד ומידת קלות־ראש שצימחו את הסבך המופרך־המדהים" ומסיים בדרישה ל"מסקנה מעשית".
האדם השלישי.
אברי אלעד, מפעילן הישראלי של החוליות במצרים, שכונה "האדם השלישי", הגיע לישראל אחרי שנותר שבועיים במצרים בלא שנעצר. תחילה נחשב לגיבור, אך בשנת 1958 בעת ששהה בחו"ל גברו החשדות שפעל כסוכן כפול, והוא שהסגיר את אנשיו למצרים. הוא פותה לחזור לארץ נעצר, נחקר והועמד למשפט בדלתיים סגורות. במהלך משפטו, טען שבצה"ל זויפו מסמכים, וניתנו עדויות שקר במטרה לטייח את האחריות לעסק הביש. טענה זו החלה ויכוח פוליטי נוקב בשאלת האחריות לפעולה זו, ויכוח שזכה לכינוי - "הפרשה", ולאחר מכן "פרשת לבון". השאלה שייצגה ויכוח זה במלוא עוזו הייתה "מי נתן את ההוראה?".
לאחר התפטרותו של לבון בתחילת פברואר 1955, מונה בן-גוריון לשר הביטחון במקומו, וב-21 בפברואר נבחר מחדש גם לתפקיד ראש הממשלה. בספרו "דברים כהוויתם" כתב בן-גוריון:
20 שנה מאוחר יותר, בשנת 1975 פורסמה בעיתון המצרי אל אהרם הטענה שאלעד, או בשמו המקורי אברהם זיידנברג, פעל כסוכן כפול. עם השנים נאספו עדויות רבות לגבי עברו המפוקפק לכאורה של אלעד, כולל בידוי פרטים מעברו, ופעילותו כגנב כפייתי ונוכל לאורך השנים. התברר שאלעד הודח מקצונה ופיקוד מספר פעמים בצבא הבריטי בפלמ"ח ובצה"ל, ואף נכלא לא פעם בעוון התנהגותו הפלילית.
ועדת כהן.
עתה בתפקיד ראש הממשלה ושר הביטחון, בן-גוריון דרש מהרמטכ"ל חיים לסקוב להקים ועדת חקירה צבאית בעניין זיוף המסמכים ו"האדם השלישי", שהיה קשור ב"עסק הביש". בראש הוועדה, שהוקמה בעת שהותו של לבון בחו"ל, עמד שופט בית המשפט העליון חיים כהן. לבון, על ידי מזכירו, ביקש מבן-גוריון את ביטולה.
בשובו לישראל, נפגש לבון עם בן-גוריון ביום 26 בספטמבר 1960, ודרש את טיהור שמו מן האחריות ל"עסק הביש". בן-גוריון סירב ואמר לו: "פנחס, אני לא פסלתי אותך, אבל אני איני שופט, ואיני יכול לזכות אותך". לבון פירש זאת כהתחמקות, ותקף בחריפות את שמעון פרס, שהיה מנכ"ל משרד הביטחון בתקופת "העסק הביש", ואת מי שהוזכר רק בכינוי "הקצין הבכיר", בנימין גיבלי, שעמד בראש אגף המודיעין של צה"ל, אשר טען שקיבל את ההוראה, בעל פה, משר הביטחון לבון.
ועדת הבירור שמינה הרמטכ"ל חיזקה בממצאיה את טענותיו של לבון אך לא הגיעה למסקנה חד-משמעית, ובכל מקרה בן-גוריון דחה את ממצאי הוועדה.
ועדת החוץ והביטחון.
לבון החליט לפנות לוועדת החוץ והביטחון. ב-4 באוקטובר העיד בפניה ומתח ביקורת על בן-גוריון. כשנודע לבן-גוריון תוכן עדותו, הפך הקרע הסמוי ביניהם לריב קשה. לבון העיד בארבע ישיבות של הוועדה: ב-4, 10, 17 ו-20 באוקטובר. הוא גולל בהן את גרסתו ל"עסק הביש" ודחה את ההצעה לחקירה משפטית. בין היתר, אף איים: "יש לי חומר שלא הראיתי לאיש, ואני לא מתכוון להראותו. אם יגיעו מים עד נפש, ייתכן שלא תהיה לי ברירה". הוא סירב לספר כיצד הגיע אליו החומר. דיוני הוועדה היו אמנם סודיים, אולם דיווחים מדבריו פורסמו בעיתונים וחוללו רעידת אדמה פוליטית. דיווחים אלה היו מצונזרים וכללו שמות-צופן מוסכמים. הציבור הרחב לא יכול היה להבין על איזו פרשה מדובר, אולם הבין כי מדובר בשבר גדול בצמרת מפלגת השלטון. מאיר יערי ויוחנן בדר כינו את פרשת לבון "דרייפוסיאדה" ובכך דימו את הפרשה לקנוניה האנטישמית בפרשת דרייפוס. הנהגת מפא"י החליטה לעשות כל שביכולתה כדי להוציא את הטיפול בפרשה מידי הוועדה ולהשתיק את הפרשה, אולם בן-גוריון החליט לנטוש את עמדתו הנייטרלית ולצאת למאבק גלוי נגד לבון.
ועדת השבעה.
באוקטובר 1960 הגיעו הדברים לידי כך שבן-גוריון סבר כי יש לחקור את הפרשה באמצעות ועדת חקירה משפטית, בעוד שצמרת מפא"י ביקשה לסיים את הדיון בפרשה.
אשכול חתר לפשרה, על פיה העניין יסתיים בלי שחקירתו תמצה את פוטנציאל ההרס שלה. בן-גוריון, מצדו, היה נחוש למצות את החקירה עד תום. שתדלנותו של אשכול הביאה להקמת "ועדת השבעה" – ועדה של שבעה שרים מכל מפלגות הקואליציה. הוועדה כללה את שר המשפטים פנחס רוזן, נציג המפלגה הפרוגרסיבית שכיהן כיו"ר הוועדה, ואת השרים לוי אשכול ובכור-שלום שטרית נציגי מפא"י, ישראל ברזילי נציג מפ"ם, יצחק בן-אהרן נציג אחדות העבודה, משה חיים שפירא נציג המפד"ל ובנימין מינץ נציג פועלי אגודת ישראל. בן-גוריון נמנע מלהגיע לישיבת הממשלה שבה הוחלט על הקמת הוועדה, אך קיבל את עצם הקמתה, אולם לא הכיר בסמכותה כוועדת חקירה שמתפקידה לקבוע עובדות בדבר זכאותם או אי-זכאותם של לבון או של בנימין גיבלי.
ב-25 בדצמבר 1960 הגישה ועדת השבעה את מסקנותיה, שבהן נקבע פה-אחד שלבון לא נתן את ההוראה, ואף לא ידע על הפעולה במצרים. אלו הסתמכו, בין היתר, על הודאת המזכירה דליה כרמל כי זייפה מסמך המזכה את ראש אמ"ן גיבלי ומטיל את האשמה על פנחס לבון, וזיכו את לבון מכל אשמה. על פי הסופר שבתי טבת בספרו "עונת הגז", חילוקי הדעות בין אשכול ובין בן-גוריון בעניין זה נבעו מפערי מידע: דליה כרמל הייתה באותו הזמן בקשר קרוב עם אשכול, וסיפרה לו כי אכן זייפה את המסמך לדרישת גיבלי (בוועדה טענה כי זייפה את המסמך, אך בחקירת המשטרה לאחר מכן חזרה בה), וכך היה אשכול משוכנע כי גיבלי פעל מאחורי גבו של לבון. בן-גוריון – שאשכול לא גילה לו את המקור שלפיו קבע את עמדתו – טען כי אין לחייב אדם או לזכותו שלא על פי הליך משפטי או ועדת חקירה משפטית.
אי קבלת מסקנות ועדת השבעה התפרשה על ידי רבים כהטלת דופי בשבעת השרים (ובראשם אשכול) אשר ישבו בוועדה, דבר שהיה עלול להביא לסופם הפוליטי של שרים אלו, רובם בני "דור הביניים" במפא"י.
בן-גוריון, שלא הכיר עקרונית בסמכותה של ועדת פוליטיקאים לחרוץ דין אדם לשבט או לחסד, לא קיבל ממילא את מסקנות ועדת השבעה, וב-31 בינואר 1961, לאחר חודש רצוף סכסוכים ועימותים, הגיש את התפטרותו לנשיא המדינה, אך נותר בכהונתו עד 1963.
ועדה משפטית.
בן-גוריון לא הסכים לכך שוועדת שרים תיתן זיכוי לשר, ודרש שקביעה כזו תיעשה על ידי ועדה משפטית. הוא דרש שלבון יודח מהזירה הפוליטית עד לבירור עניינו, ושקביעת ועדת אולשן-דורי אשר פסקה על תיקו (אי-הכרעה הנובע מחוסר מידע) תישאר בינתיים על כנה.
בציבור נוצר הרושם כאילו בן-גוריון רואה בלבון אויב אישי, ורודף אותו על לא עוול בכפו.
מרכז מפא"י שהתבקש להכריע בסכסוך זה, קיבל את דרישתו של בן-גוריון, ובשבת ה-4 בפברואר 1961 הודח לבון מתפקיד מזכ"ל ההסתדרות, ומחק את לבון מרשימת מועמדי המפלגה לכנסת. בן-גוריון אמנם היה הדורש העיקרי להדחת לבון, אך הצעת הפשרה של שר האוצר לוי אשכול גם היא כללה את הדחתו מתפקידים פוליטיים ומן המפלגה. כפי הנראה ההדחה לא הייתה יוצאת אל הפועל ללא שיתוף פעולה בין השניים.
פרסום ראשון בציבור.
במרץ 1964 פורסם מידע מרומז ראשון לציבור על פרטי "הפרשה". עשה זאת אורי אבנרי, בשבועונו "העולם הזה", באמצעות סיפור מתח בדיוני לכאורה שנקרא בשם "פרשת אלכסיס" ובו תיאור מאבק מודיעיני בין יוון לטורקיה, שדמויותיו ועלילתו תאמו את עובדות הפרשה והאישים שנטלו בה חלק.
בירור פנימי במפא"י.
דרישתו של בן-גוריון לוועדת חקירה משפטית והתנגדותו העקרונית לתעודת זיכוי הניתנת לפוליטיקאי על ידי ועדת פוליטיקאים, לא הייתה מובנת לציבור באותה עת ו"הפרשה" (או, כפי שכונתה, "פרשת לבון") פגעה ביוקרתו של דוד בן-גוריון, וכנראה, הייתה בין הגורמים שהניעו אותו להתפטר מראשות הממשלה, בשנת 1963, תוך שהוא מדגיש שהתפטרותו היא "בשל סיבות אישיות שאינן קשורות לשום בעיה ממלכתית". הוא המשיך להיאבק על דעותיו, ובפרט תקף את יורשו, שנבחר לתפקיד על-פי המלצתו, לוי אשכול.