קמחי סיכם את החיפושים בים האגאי ודיווח כי "כל אזורי הסבירות הנמוכה נסרקו ויש לחזור לנתיב ולחפש במים העמוקים". ראש מחלקת מבצעים אל"ם חיים געש שהורה לעשות תחקיר פנימי הגיע למסקנה דומה. ב-1996, מפקד חיל הים עמי אילון העמיד בראש הוועדה את תא"ל מיל גדעון רז, צוללן ותיק שפיקד בעבר על הצוללת אח"י לווייתן. רז עבר יחד עם אברהם ברקאי, סגן מפקד "דקר", את קורס החובלים ואת קורס קציני הצוללות. רז התמקד בחיפושים בלבד; את הפעילות בתחום הציבורי ומול המשפחות ריכז תא"ל במילואים גבי נווה, איש צוללות וראש מספן כוח האדם בעברו.
רז ואיילון ידעו שאין לחיל הים יכולת איתור בעומק רב, ולשם כך יידרש סיוע מציים אחרים. גדעון רז הכין בקשת סיוע למציאת "דקר" שהועברה דרך נספחי צה"ל לציי ארצות הברית, הולנד, בריטניה ורוסיה. רק הצי האמריקני הגיב ונענה לאתגר.
בנובמבר 1995 תוכננה לאיילון פגישה עם מפקד הצי האמריקני אדמירל ג'רמי בורדה, בה התכוון להעלות, בין יתר הבקשות, גם סיוע לחיפוש ה"דקר". עקב רצח ראש הממשלה יצחק רבין חזר איילון בדחיפות לארץ, והפגישה לא התקיימה. במקומו נפגש נספח חיל הים בארצות הברית, אל"ם חזי משיטה, עם אדמירל בורדה, ובהוראת איילון הציג רק בקשה אחת: סיוע למצוא את שברי "דקר".
הפיקוד על חיל הים עבר לאלוף אלכס טל. באוקטובר 1998 נענה שר הביטחון יצחק מרדכי לפניית משפחות הדקר והכריז על פרס כספי של 300,000 דולרים, למי שיביא נתונים שיסייעו לפתרון התעלומה. הודעת הפרס פורסמה בעיתונים בטורקיה, יוון, קפריסין, צרפת ורוסיה. ועדה בראשות גדעון רז נקבעה כדי לטפל בידיעות שיגיעו ולהמליץ על מתן הפרס. מידע ממשי על ה"דקר" לא הגיע, והסכום שהוקצב לא שולם. שולמו סכומים קטנים ליזמים שונים.
פגישה בין אדמירל ג'רמי בורדה למפקד חיל הים אלכס טל התקיימה כאשר הגיע לביקור בישראל. בורדה היה ממוצא יהודי, והוא היחיד שהגיע לתפקיד מפקד הצי האמריקאי CNO מתוך שורות אנשי הצוות ולא כצוער במכללה לקצונה ימית. בשיחה אישית עם מפקד חיל הים סיפר ג'רמי בורדה על שאיפתו לסייע לחיל הים הישראלי, ואלכס טל ביקש לקבל סיוע במציאת "דקר". האדמירל לא הופתע מהבקשה והבטיח להעמיד את הציוד והידע של הצי האמריקני לצורך החיפושים.
אדמירל בורדה הלך לעולמו במאי 1996 ולא ראה בתוצאות הוראותיו. הצי האמריקני מילא את ההתחייבות והודיע שניתן יהיה להשתמש בצוללת המחקר הגרעינית של הצי NR1 לפרק זמן מסוים. הצי האמריקני המליץ לחיל הים על מספר חברות שהתמחו בגילוי עצמים בעומק הים, ביניהן חברת נאוטיקוס. לאחר הסידורים הכספיים הקים גדעון רז ועדה מקצועית, אליה צרף את רב חובל אברהם אריאל מצי הסוחר ואת דורון עמיר ויחיאל געש מחיל הים. בעצת אדמירל קרול מצי ארצות הברית, צורפו לוועדה מנהל חברת "נאוטיקוס" דייוויד ג'ורדן והמהנדס הראשי טום דטויילר.
תיקון המסקנות מהמצוף.
אנשי "נאוטיקוס" שהיו מודעים היטב לכך שתופעת הקריסה כוללת מעיכה וגם פיצוץ, הזמו את המסקנה לגבי הימצאות הדקר במים רדודים. הם העלו את האפשרות שהמצוף ניתק מהצוללת בעת האירוע ביחד עם תוף הכבל שלו. המשקל הכולל איזן את כוח הציפה. המצוף ריחף מתחת לפני המים כשהכבל פרוש. כך נסחף זמן רב בזרמי הים עד שהתוף נתקל בקרקעית ועגן זמנית בקרבת החוף. במצב עגינה הכבל נשחק עד שנקרע לגמרי. המצוף שהשתחרר הגיע לחוף רצועת עזה בו נמצא.
בסיכום הדיון נכתב:
המשמעות הייתה התמקדות בגזרת חיפוש מצומצמת במרכז השטח שצוין ב"דו"ח אובדן הדקר" על ידי האלוף שלמה אראל, במרץ 1968, כשטח הסביר לחיפוש. עומק הים בגזרה זו כ-3,000 מטרים.
צוללת המחקר NR1 הגיעה לאזור ועסקה בחיפושים במשך כחודש. היות שיכולת הגילוי שלה הייתה מוגבלת עד עומק ים של 1,000 מטרים היא הופנתה לחיפוש בחופי קפריסין ומצרים, אך ללא תוצאות.
שמועות תוצרת עצמית.
שילוב אמצעי הצי האמריקאי לחיפושים בעומק רב ותהליך ההתמקדות שנעשה בחיל הים, לא פורסמו לציבור. חרושת השמועות המשיכה במלוא עוזה. שמועות אלה הגיעו לשיאן בשנות התשעים.
ב-1997 הופיע הספר "דקר וסיפורה של שייטת הצוללות", שנכתב על ידי אל"ם במילואים מייק אלדר, יוצא חיל הים. ב-1998 הופק סרט הטלוויזיה "הדקר נמצאת כאן", על ידי יוצא חיל הים, איש הטלוויזיה מיכה לימור. בכישרונו שכנע לימור את צופי הסרט שיש לחפש בחופי מצרים. לספר ולסרט לא הייתה השפעה על תהליך החיפושים. עם זאת, חיל הים, שכבר עשור קודם לכן החליט שאין הגיון לחפש את השברים בקרבת חוף המצרי, ושב-1997 החליט להתמקד בנתיב הצוללת המקורי, הועמד שוב במצב מביך.
מציאת השברים.
בקיץ 1998 הותקן סונאר סורק צד למים עמוקים על ספינה ישראלית, והופעל על ידי יחידה של הצי האמריקני. היחידה סרקה את אזור C וחלק מאזור B (ראה במפה), אך לא היו ממצאים. בסוף 1998 הוציא משרד הביטחון מכרז לחברות מסחריות אמריקאיות לביצוע החיפוש במעמקי הים, ובו זכתה חברת נאוטיקוס בשל הסכמתה לדרוש את התמורה רק לאחר הצלחתה במציאת שרידי ה"דקר".
ב-1999 החלו החיפושים. חברת "נאוטיקוס" התארגנה למבצע עם מומחים וציוד, חלקם גם מחברות אחרות, כולל סונאר סורק צד ורובוט תת-מימי מדגם Remora 6000. שתי ספינות גרר מיוחדות נשכרו בקפריסין: הפליינג אנטרפרייז לגרירת הסונאר, והאיאס המצוידת גם במערכת ממוחשבת מיקום דינמי המאפשרת את שמירת מיקומו של כלי שיט גם ללא עגינה בקרקעית, לצורך עבודה עם רובוט הצילום.
התארגנות נעשתה בנמל לימסול, ובתחילת חודש מאי יצאו הספינות לים. לאחר כמה ימים של טיפול בתקלות חשמליות בסונאר, כוונו הספינות על ידי חיל הים לגזרה C הקטנה. לאחר מכן עברו לגזרה B. רוחב התמונה המתקבלת מהמכשיר היה 1,500 מטרים. במהלך הסריקה היה על הסונאר להמצא בגובה 60 מטר מעל הקרקעית. מכיוון שעומק הים במקום הוא כ-3,000 מטרים, היה צורך לפרוש את כבל הגרירה באורך כפול. גרירת הסונאר סורק הצד נעשתה לאיטה, במהירות שבין 1.5 ל-3 קשר. נדרשה זהירות רבה שכן נגיעת הסונר בקרקעית משמעותה אובדן המכשיר. המטרות שהתגלו קיבלו מספר זיהוי והערכה ראשונית, והנתונים שנאגרו במחשב עברו ניתוח נוסף. גזרת החיפוש חולקה ל-16 רצועות כאשר במהלך החיפוש האיטי התגלו נותחו ותויגו 320 מטרות של הסונאר. מתוכן היו 19 מטרות שעליהן הורד רובוט הצילום לזיהוי.
ברצועה האחרונה של החיפוש, חש רס"ן יחיאל געש, קצין חיל הים המלווה, מחויבות לגבי אחד ההדים שהסתמנו על הצג. ספינת החיפושים איתרה אותו בנתיב החוזר וההדים אושרו כשברי אונייה, "אפשרות לצוללת". הרובוט התת-מימי הורד מעל העצם וגילה חלק מגשר צוללת עם שרוול הוצאת הלוחמים מאלומיניום. אחריו התגלה גוף הצוללת עם כיפת הסונאר האופיינית לצוללות T. באתר הנמצא במחצית הדרך בין כרתים לבין חיפה אותרו שברי ה"דקר" ב-28 במאי 1999 כשהם מונחים על קרקעית הים בעומק של 2,950 מטר.
השברים נמצאו כ-145 מיילים ימיים מזרחית מהאתר האחרון שדווח. קרוב מאוד לאתר המשוער בו אוכן השידור המקוטע מהמצוף בעת החיפושים. המקום הוא במרכז "השטח הסביר לחיפושים", כפי שהוגדר ב"מסמך אראל" ממרץ 1968. בנתיב הדרומי ביותר במרכז הגזרה הממוקדת לחיפושים שנקבעה בסיעור המוחות ב-1997. חיל הים דרש מכל העוסקים בחיפושים, להימנע ממסירת האתר המדויק בו נמצאו השברים, ונמנע מכך בעצמו.
למחרת זוהו השברים בוודאות באמצעות רובוט צילום תת-מימי, כשייכים ל"דקר". משימת הזיהוי הוטלה, על ידי מפקד חיל הים, על יו"ר וועדת איתור ה"דקר" תא"ל (מיל) גדעון רז, שצירף אליו את מפקדי שייטת הצוללות בעבר, אל"מים (מיל) דורון עמיר ומיכאל קיסרי. יצאו בספינת טילים אל אתר הגילוי. קבוצת המפקדים ראתה את צילומי הרובוט ורז דיווח את השיוך הוודאי של השברים ל"דקר" למפקד חיל הים אלכס טל. מפקד החייל מצידו קיבל את המסקנה והורה על העברת המידע למשפחות צוות ה"דקר".
כלקח מן החוויה הקשה שעברו המשפחות ב-1968, הופעל נוהל שנקבע במספן כוח האדם: לקראת כל חיפוש מונו מספר קצינים וקצינות שהיו בכוננות מיידית להגעה למפקדה. לכל קצין היה דף קשר לקבוצת משפחות. משהוזנקו הקצינים היה עליהם להתייצב במפקדה ולהקריא את הנוסח האחיד שקיבלו לבני המשפחות שברשימתם. תהליך זה בוצע במלואו ביום שישי, י"ג בסיוון תשנ"ט, 28 במאי 1999.
חקירת השברים.
התארגנות.
מיד עם מציאת הצוללת הוחל בחיל הים בניסיון לנתח את המידע המוקלט והמצולם, אשר התקבל מתהליך זיהוי ה"דקר". לצורך ניתוח הממצאים כונס פורום משותף של מהנדסים וותיקי שייטת הצוללות, אשר ניסו לזהות פרטים חיוניים בצילומי הווידאו התת-ימיים. אולם, כמות ואיכות הצילומים אשר נעשו למטרה של זיהוי הצוללת בלבד לא אפשרה מתן תשובות חד משמעיות לגבי שתי שאלות עיקריות שנותרו תלויות בחלל האוויר: מה הייתה סיבת הכשל שהביאה לאובדן הצוללת, והאם נותרו שרידים מצוות הצוללת באתר הטביעה.
מתיעוד הווידאו ושרטוט סכימתי שהכינה חברת "נאוטיקוס" ניתן היה להבחין כי גוף הצוללת נותר שלם ברובו, למעט ירכתי הצוללת, אשר ניתקו ממקומם ונחו בצמוד למרכז הצוללת, וסנפיר הצוללת, אשר נשבר ונטה על צידו. הרושם הראשוני היה כי גוף הצוללת נותר שלם, אולם עיון מעמיק בתיעוד העלה כי נזק רב נגרם לשלושת מדוריה המרכזיים של הצוללת, ובמספר מקומות נפרץ גוף הלחץ, וניתן היה להבחין בחלקי הצוללת הפנימיים. גשר הצוללת וחלקי סיפון זוהו, כשהם פזורים על קרקעית הים, לאורך מאות מטרים בנתיב שקיעתה של הדקר.