טבק הרכיב צוות מצומצם ביותר מאנשי המשלחת ושלח אותם לחנויות לקנות מזון להפלגה, ובמקביל הצליח לראות מפה מטאורולוגית של הצי הצרפתי שחזתה מזג אוויר סביר. קצין הלוגיסטיקה, רס"ן חיים שחק, הפעיל את קשריו והצליח לקבל אישור מכס ליציאת אח"י סער. הוא הסביר את הדחיפות בבקשה בשאיפה לנצל הפוגה במזג האוויר, ומכיוון שאנשי המכס בשרבור עדיין לא קיבלו הוראות על החמרת האמברגו הצרפתי על ישראל, נחתם אישור המכס.
יציאת כלי שיט מה חייבה פתיחת גשר, אותו ניתן היה לסגור בקלות ולמנוע את היציאה מן הנמל. טבק שכנע את הקצין התורן לשמור את הגשר פתוח, ובשבת, 4 בינואר 1969, בשעה 16:30 הפליגה אח"י "סער" לים בפיקוד משה טבק. למרות התחזית האופטימית נתקלה אח"י "סער" בדרכה בגלים גבוהים. גם אח"י עכו, שיצאה לפניה, נתקלה בים סוער במפרץ ביסקאיה, ולאחר מכן נקלעה לסערה מערבית לפני גיברלטר. הספינה המתינה יממה בעגינה בחוף פורטוגל, שם עגנו גם אוניות אחרות שהיו בדרכן לים התיכון והמתינו לשוך הסערה. עם היחלשות הסערה המשיכה אח"י עכו לגיברלטר, שם קיבלה הוראה להמתין לאח"י סער.
מפקד המשלחת אל"ם הדר קמחי שהפליג עם אח"י עכו ירד בגיברלטר וחזר לשרבור. מיד עם שובו זומן קמחי אל האדמירל הצרפתי, מפקד האזור הימי. האדמירל חשש שיציאת אח"י סער לפני הודעת האמברגו הייתה עלולה להתפרש כאילו אנשי הצי הצרפתי במקום סייעו לכך, והכין לקמחי קבלת פנים הפגנתית. הוא הקריא את הפסוקים בנוכחות סגל קצינים רחב, והביע באוזניו מורת רוח. לסיכום הודיע כי אישורי הכניסה לישראלים לארסנל מבוטלים. גם בפריז נקרא מרדכי לימון אל מפקד חיל הים הצרפתי. בחדר נכחו פקידי ממשל בכירים, שהעלו טענות על יציאת הספינות ללא הודעה מוקדמת. לימון אמר כי אכן הייתה חריגה מהנהלים, אך לעומת זאת הצרפתים הפרו חוזה חתום. תשובת האדמירל שנמסרה בארבע עיניים הייתה .
החלטה להמשיך בבנייה.
במקביל לשיחות הקשות בפריז ובמפקדת הצי בשרבור, הוזמן הדר קמחי באותו יום לפגישה עם אדם שהזדהה כנציגו של ראש עיריית שרבור. האיש סיפר לקמחי כי אנשי שרבור, ברובם מצביעי מפלגת השלטון, הם שהשפיעו בעבר על השמטת הספינות מן האמברגו. כעת, בשל החמרת האיסור, הם מודאגים מהפסקת הבנייה העלולה להביא לפיטורים נרחבים של פועלי המספנה ולפגיעה בכל תושבי שרבור שכלכלתם עליה. הוא ביקש שהישראלים לא יפסיקו את הבנייה וכי ודאי יימצא פתרון יצירתי לאמברגו שאולי יבוטל. האיש הוסיף שאנשי שרבור יעזרו ככל יכולתם.
חיל הים היה זקוק לחמש הספינות שהיו עדיין בבנייה. הדר קמחי יצא לפריז ונפגש עם מרדכי לימון לטכס עצה, ומשם דיווח על השתלשלות העניינים למפקד חיל הים, האלוף אברהם בוצר. בוצר הסכים עקרונית שיש להמשיך בבנייה ומינה את קמחי לרכז את נושא המילוט. רב-אלוף צבי צור, שאישר כרמטכ"ל את רכישת הספינות, היה עתה יועץ מיוחד לשר הביטחון משה דיין, ובסיועו החליטו ממשלת ישראל ומשרד הביטחון להמשיך בבנייה בתקווה שיימצא פתרון.
המספנה עבדה במלוא הקצב. בפברואר 1969 הושקה ספינה שמינית. במאי, באוגוסט ובאוקטובר אותה שנה הושקו שלוש נוספות. לפי תנאי החוזה התשלום האחרון לכל ספינה היה צריך להיות מועבר בעת המסירה ללקוח. משרד הביטחון הפיק לקח מעסקת מיראז' 5 שנפגעה מהאמברגו הצרפתי על ישראל, שם העבירה ישראל את מלוא התמורה בתקווה לקבל את המטוסים. כאן ננקטה מדיניות שונה, ומכיוון שהספינות לא נמסרו עוכבו התשלומים. בעל המספנות, פליקס אמיו, נכנס לחובות ומימן בעצמו את המשך הבנייה ואת הרכישות שנדרשו אצל ספקים אחרים.
תכנון המבצע.
תכנון המבצע ואישורו.
שארל דה גול פרש מהנשיאות בסוף אפריל 1969. כמחליפו נבחר ז'ורז' פומפידו, שקיבל ב-15 ביוני את השלטון. בעת מערכת הבחירות הבטיח פומפידו להקל את האמברגו, ואמר לז'אן פרידמן, מבעלי רשת התקשורת אירופה 1, כי ישחרר את המיראז'ים. אך לאחר שנבחר התברר כי ההתקרבות לערבים נשארה ביסוד מדיניות ממשלת צרפת והתקווה לביטול האמברגו נגוזה. היה צורך בפעולה מתוחכמת שתעמוד בכללי המשפט ולא תפגע בחוק הצרפתי.
בעצתו של מרדכי פרידמן, מנהל חברת "נתיבי נפט" וידידו של מרדכי לימון, נבנה סיפור כיסוי כאילו נמכרו הספינות לצד שלישי. בדרך זו ניתן יהיה להוציא את הספינות מצרפת בלי שתיווצר בעיה חוקית ובלי שישראל או מספנות שרבורג יעברו על החוק הצרפתי. כך גם ייווצר הרושם הרצוי כאילו ישראל ויתרה על הספינות. אם יימצא גורם שלישי שניתן יהיה להציגו כאילו רכש את הספינות, תוכלנה הספינות לצאת מצרפת עם אישור המכס. ניתן גם יהיה להשיט את הספינות עם הצוותים הישראליים שעליהן, בטענה שהם בעלי הניסיון בהפעלת הספינות וכבר נמצאים במקום, והקונה רוצה לחסוך בזמן ולקבל את כלי השיט במהירות.
הבעיה העיקרית בסיפור הכיסוי הייתה למצוא צורך אזרחי לספינות שנבנו לפי הגדרות צבאיות. בעצת פרידמן הוצגו הספינות כמיועדות לתת שירותים לאתרי קידוח ימי וחיפושי נפט בים, וזאת מאחר שבבארות הנפט הימיות יש צורך בספינות קטנות ומהירות להובלת אנשים וציוד מהחוף.
באותה עת התגלה נפט בחופי נורווגיה, וזו נראתה מקום אפשרי לביסוס סיפור הכיסוי. מרדכי פרידמן קישר את לימון עם איש הספנות הנורווגי מרטין סיאם, אותו הכיר כאשר השתתף בבניית קו צינור אילת אשקלון. סיאם היה בעברו איש המחתרת הנורווגית, ושימש בתפקיד מנהל כללי של מספנות אקרס , המספנות הגדולות ביותר בנורווגיה. סיאם נפגש בקופנהגן עם פרידמן ולימון, שמע את בקשתם לתיווך ואמר שעליו להתייעץ. הוא שוחח עם בעלי החברה באוסלו וגם עם מילה ברנר, איש ים ישראלי שהיה, בין השאר, ממקימי "החברה הימית להובלת פרי". ברנר הזמין אוניות במספנות אקרס והיה לידידו האישי של סיאם. ברנר, שרצה בהצלחת חיל הים וגם בשמירה על שלום ידידו, יעץ לסיאם להחליט לפי מצפונו. לאחר שקיבל את אישור בעלי המספנות, נתן מרטין סיאם את הסכמתו לסייע.
סיאם הציג עצמו כמייצג חברה רשומה בפנמה, ושמה Starboat S.A. החברה הציגה עצמה כמבקשת לרכוש ספינות לצורכי שירות לקידוחי נפט. סיאם לא מסר היכן יפעלו הספינות וברישומים לא הופיעה אף חברה נורווגית. כל עבודת הניירת נעשתה מהמשרד בפריז, וסיאם אישר למרדכי לימון לפעול לפי הבנתו, כך שכל החוזים והמכתבים נוסחו בפיקוחו האישי של לימון. בניירת נרשם "סטארבואט - אוסלו" עם תיבת דואר. החברה נרשמה בפנמה כמקובל ברישום אוניות תחת דגל נוחות, ולחברה הפנמית היה נציג באוסלו שקישר בעסקה.
על פי תוכנית זו לא הייתה אמורה להתהוות הפרה של החוק הצרפתי. השלטונות בצרפת שהכירו את סיאם קיבלו את הרושם שהספינות נמכרו לגורם שלישי והן אכן יוצאות לנורווגיה, לאחר שישראל ויתרה עליהן. הספינות נמכרו ל"סטארבואט" כדי להפעילן לשירות הפקת נפט, וכך ניתן היה לתת לספינות את אישור המכס. חברת "סטארבואט" הייתה אמורה להציג את הדברים כאילו הספינות נמכרו לחברה היושבת בלונדון, אם כי לא נאמר בשום שלב שקידוחי הנפט יהיו דווקא בנורווגיה; הצרפתים קיבלו את הרושם שהספינות מפליגות לנורווגיה, אך נאמר להם כי לקונה יש זכות להודיע היכן הוא רוצה לקבל את הספינות. מאוחר יותר נחתם חוזה בין סטארבואט לנתיבי נפט שלא הוצג לצרפתים. כך נבנה מעטה שיכול לעמוד גם במבחן המשפט הימי.
מרדכי לימון נפגש בישראל עם מפקד חיל הים, אברהם בוצר, והציג בפניו את עיקרי התוכנית למילוט הספינות. בוצר אישר את התוכנית ומינה את הדר קמחי, שנכח אף הוא בפגישה, כאחראי מטעם חיל הים לביצועה.
באותה עת היו למשרד הביטחון עדיפויות אחרות ברכש מצרפת, ובראשן עסקת מטוסי המיראז' 5 שהייתה בהיקף גדול הרבה יותר. עסקת המיראז'ים אומנם בוטלה, אך התעשייה האווירית החלה בייצור מטוסי נשר, ייצור שדרש שיתוף פעולה חשאי והעלמת עין של הרשויות בצרפת. הסמנכ"ל לתפקידים מיוחדים של משרד הביטחון הודיע ללימון במכתב כי "שקלנו והגענו למסקנה שאי אפשר להעלות לדיון אפשרות קניה של חברה פיקטיבית", אך שיחת טלפון של לימון עם עוזר שר הביטחון, רב-אלוף במילואים צבי צור, שינתה את המצב ומשרד הביטחון הסכים לקדם את התוכנית. עם זאת, ראש ממשלת ישראל גולדה מאיר ראתה חשיבות בהמשך היחסים עם צרפת והתנתה את המבצע בכך שלא יפגע בחוקי צרפת.
מבצע מילוט הספינות תוכנן בידי מרדכי לימון, שתכנן והוביל את ההטעיה עד אישור היציאה מצרפת. שמירת כושר ההפלגה של הספינות, אחזקתן ואחזקת הצוותים היו בניהול משלחת חיל הים בצרפת, ואילו הכנת הנתיב, תיאום אוניות התדלוק, הפיקוד על היציאה משרבור וההפלגה היו באחריות חיל הים. בניגוד לסיפורים שהופצו, המוסד למודיעין ולתפקידים מיוחדים כלל לא היה מעורב במילוט ספינות הסער משרבורג. גם שגרירות ישראל בפריז כמעט ולא שותפה בעניין.
"מכירת הספינות".
בעלת מספנות SAMT ביקשה מהוועדה הבין-משרדית ליצוא אמצעי מלחמה בצרפת רשות לנהל משא ומתן עם קונים פוטנציאליים. מרדכי לימון התבקש על ידי הצרפתים שישראל תוותר על הספינות. לימון השיב בשלילה, אך הודיע שיעביר את הבקשה לרשויות בישראל.