בראשית מאי אותה שנה התירו הבריטים ליוסף לישנסקי, שהיה במצרים לצורך פעילות ארגון ניל"י, לצאת למקום ולחפש אחר גופתו של פיינברג. שישה ימים לאחר מכן נפגש לישנסקי עם אהרן אהרנסון והודיע כי איתר את המקום המדויק בו נתקלו בבדואים, אך אין שום אפשרות למצוא את הגופה, כיוון שבוצעו במקום עבודות ביצור נרחבות ונבנו פסי רכבת מעל הקבר. המחקר המודרני קבע שלישנסקי טעה, אך לא באופן ניכר: מקום קברו של אבשלום היה קרוב מאוד אל פסי הרכבת והכביש אשר נבנו שם. ביומנו רשם אהרנסון ב-8 במאי את המסקנה: .
כשישה חודשים לאחר הרצח עצרו הבריטים את מוח'תאר העיירה ח'אן יונס, שהיה מעורב במעשה הרצח אך סירב להודות בכך בחקירתו, והוא שוחרר מחוסר ראיות.
במשך הזמן שבין היעלמו של אבשלום לבין נפילתה של ניל"י בידי העות'מאנים לא ידעו גם אנשי ניל"י עצמם (פרט ליחידים, ובהם יוסף לישנסקי, ואהרן ושרה אהרנסון) היכן אבשלום. דבר זה גרם לנעמן בלקינד, שחש שמשהו אינו כשורה, לצאת למצרים לחפש את אבשלום, והביא על ניל"י, בסופו של דבר, את קִצהּ. גם נעמן לא הצליח לפתור את תעלומת אבשלום, ואפילו לא הצליח לגלות כי מת: בצוואתו, שנכתבה זמן קצר לפני הוצאתו להורג, הזכיר את אבשלום בין שאר ידידיו וקרובי משפחתו החיים.
יעקב ירושלמי, חייל יהודי יליד טורקיה, אשר שירת בצבא העות'מאני במלחמת העולם הראשונה באזור רפיח, הוזעק על ידי בדואים או חיילים טורקים לערוך טקס קבורה יהודי להרוג שזהותו לא הייתה ידועה לו. הוא אמר קדיש ושמע ישראל ליד הקבר, אך נמנע מאמירת אל מלא רחמים, כיוון שלא ידע את שם המת. הייתה סברה כי ההרוג הוא פיינברג, אך שלמה בן אלקנה דחה אותה בספרו "אבשלום פיינברג שב מן המדבר" על ידי מספר נימוקים (עיקר טענתו היא, שלא שמע מן הבדואים על כך, וששלדו של פיינברג היה קבור בקבורה לא יהודית).
מחקרו של בנימין רן.
בסוף שנות ה-20 החל הסופר יעקב יערי-פולסקין בכתיבת ספרים על אודות ניל"י, ובשנת 1930 התפרסם ספרו הראשון, "מרגלים או גיבורי המולדת?". בנימין רן, מהנדס שעבד במערכת הרכבות בחיפה, קרא את הספר והחליט לנסות ולחפש את קברו של אבשלום. הוא ביקש וקיבל העברה לאזור רפיח, ושם ניסה לדובב את הבדואים ולגלות מה אירע. רן יצר קשרים טובים מאוד עם הבדואים באזור, והם הובילו אותו אל מקום שנקרא בפיהם 'אלקבר אליהודי' – "הקבר היהודי". מעל הקבר צמח תמר, ככל הנראה מגלעין תמר שהיה בכליו של פיינברג בעת שנרצח. הוא צילם את התמר (ראו תמונה), וחשב שבכך נפתרה התעלומה. מיד לאחר מכן, במרץ 1931, נסע לזכרון יעקב, פנה אל אלכסנדר אהרנסון, גילה את ממצאיו והראה את התמונה שצילם. אהרנסון פקפק בדבר ופנה אל קצין בריטי ממכריו, שיבקש מן המושל הבריטי של סיני, מייג'ור קלוד ג'רוויס לבדוק אם נכונים דברי רן והאם אמנם טמונה גופת פיינברג באותו מקום.
ככל הנראה, במהלך הפנייה למייג'ור ג'רוויס חל שיבוש מסוים, וכתוצאה מכך, במקום לנסות לאתר את הדקל ברפיח שאותו מצא רן, הוא עשה ניסיונות לאתר את הקבר באזור שיח' זוויד, במרחק של כ-15 קילומטרים משם. ניסיונותיו לא צלחו, והצעת זיהוי מקום הקבר בידי בנימין רן נדחתה שלא בצדק. רן עצמו, שככל הנראה לא ידע על החקירה של מושל סיני הבריטי, חש כי אין דעת המשפחה נוחה מחשיפה מחדש של הקבר, ואין לה עניין לפתוח מחדש את הפצעים ולעורר מחדש את הטרגדיה, ועל כן ויתר ולא התעקש על חקירה מחודשת.
כך שקע העניין ונשכח למשך זמן רב. בהדפסה הראשונה של הספר "ניל"י – תולדותיה של העזה מדינית", בשנת 1961, מתואר מותו של אבשלום פיינברג במילים:
מציאת הקבר על ידי שלמה בן אלקנה.
ב-21 בינואר 1966, יום למחרת יום השנה ה-49 למותו של אבשלום, נתפרסמה בעיתון "הארץ" כתבה של העיתונאי אורי קיסרי שעסקה באבשלום ובנסיבות מותו. את הכתבה קרא גם פקד שלמה בן אלקנה, קצין במשטרת ישראל וחוקר תולדות ארץ ישראל, אשר התמחה בפענוח תעלומות היסטוריות מסוג זה, ואף פתר, שנים מספר קודם לכן, פרשות נעדרים בעלות קווים דומים לזו (פרשת לזרוביץ-קירז'נר, פרשת היעלמותו והתאבדותו של החייל חיים יערי ועוד). הוא החליט לנסות ולפתור גם את התעלומה הזו, ולמצוא את קברו של פיינברג. הוא פנה לאורי קיסרי, וכתב לו:
על פי עצת קיסרי, למד בן אלקנה על אודות אבשלום פיינברג ומה שהיה ידוע על מקום קברו. הוא הבין כי מושל סיני הבריטי, קלוד ג'רוויס, לא הצליח למצוא את הקבר בראשית שנות ה-30 משום שבגין טעות בדיווח חיפש אותו בשייח' זוויד ולא ברפיח, והבין כי חיפוש נוסף בסביבות רפיח עשוי להוביל למציאת הקבר. באותה עת רפיח הייתה שטח בתחום מצרים, ועל כן נטה בן אלקנה לנהל את החקירה בחשאי: הוא נפגש עם שני שייח'ים בדואים ישראלים שהכיר, ובירר אם יוכלו לשלוח שליח בדואי שיחצה את הגבול לאזור הקבר, יוציא את העצמות מתחת לדקל ויביאן לשטח ישראל, תמורת פרס כספי. הם השיבו שזה אפשרי. לאחר בירור זה פנה אל בני משפחתו של אבשלום, בניסיון לרתום גם אותם לעניין. הם הביעו התנגדות חריפה, בנימוק שאין לדעת מה יביא השליח הבדואי, ולא ניתן לסמוך על זיהוי העצמות כאלו של אבשלום. מעבר לזה, טענו כי הם התרגלו למצב שבו אין קבר מסודר לאבשלום.
דחייה זו לא הרתיעה את בן אלקנה, היות שחשב כי . הוא רצה לגייס את משאבי המדינה לכך, לקבל ממנה סיוע כספי ולדאוג לעריכת לוויה צבאית כאשר יוחזרו העצמות. על כן ניסה ליצור קשר עם ראש ממשלת ישראל לוי אשכול, ולקבל את אישורו. ניסיונותיו, שנמשכו כמה חודשים, לא צלחו. באוגוסט אותה שנה אסר עליו מפכ"ל המשטרה פנחס קופל להמשיך בחקירת הפרשה, עקב תלונה שהגיש נגדו איש "ההגנה" יוסף קוסטיקה, כשחקר את פרשת כ"ג יורדי הסירה במקביל לניסיון להביא את עצמות פיינברג.
מציאת השלד.
לאחר מלחמת ששת הימים הועבר בן אלקנה מהמשטרה לצה"ל, והפך יועץ לעניינים ערביים בלשכת אל"ם מרדכי גור. כיוון שבעת זו היה שייך לצה"ל, ויתר על כן - השטח שבו נמצא קבר אבשלום היה בידי ישראל – דבר לא מנע ממנו לפעול. הוא יצר קשר עם שייח' פרייח, בדואי מרצועת עזה שעמו היה ביחסים טובים עוד מימי מלחמת סיני, וביקש ממנו לנסות ולברר עם בדואים בני משפחת אבו צפרה משבט אל-סננה שבמטה אלרמלייאת באזור רפיח, האם הם יודעים משהו על רצח אבשלום. בני המשפחה הראו לבנימין רן עוד ב-1931 את הדקל שצמח מעל קבר אבשלום, ובן אלקנה הניח שבשלב זה עדיין אפשר למצוא עדי שמיעה ואולי אף עדי ראייה לרצח. השייח' פרייח בירר ומצא בדואים אשר הכירו את המעשה וסיפרו פרטים על אודות התקרית.
מתיאוריהם את תקרית הרצח היה ברור למדי כי מדובר בפיינברג, ונתבררו פרטים שלא היו ידועים עד אז לגבי הרצח. יותר מכך: הם הובילו אותו אל הדקל שצמח מעל לגופתו של אבשלום פיינברג. ב-29 באוקטובר 1967 הגיע בן אלקנה, מלווה באנשים נוספים, אל הדקל שצמח מעל שלדו של אבשלום. במשך יומיים הם חפרו, והוציאו את השלד ביחד עם הדקל. לאחר מכן הם מסרו אותם לבדיקה במכון הפתולוגי באבו כביר.
בד בבד עם הבדיקה, שנמשכה למעלה משבוע, פורסמו בעיתונים בישראל ידיעות וכתבות על פיינברג ומציאת שלדו. בינתיים הצליח בן אלקנה לגבות עדות מבדואי בן 80, שהשתתף במעשה הרצח בעצמו, וכך סיפר:
זיהוי ודאי.
הבדיקה במכון הפתולוגי העלתה כי השלד שנמצא מתחת לדקל הוא שלדו של פיינברג, מעבר לכל ספק: השלד השתייך לזכר כבן 30 (פיינברג היה כבן 27 כשנרצח); הערכת גובהו תאמה כמעט לגמרי את זה של פיינברג; רסיסי עצם קטנים באחת מאצבעות היד העידו על פציעה באצבע – כזו חווה אבשלום כשפלט אקדחו קליע בשעה שניקה אותו, ב-1911; סתימות רבות בשיניו של הקבור העידו כי אין מדובר בערבי תושב האזור, וחריץ ייחודי באחת משיניו היה זהה לזה שהיה לפיינברג, שנפצע מברזל בצעירותו. בשלד נמצאו שלושה נקבים של קליעים – שניים בגולגולת (נקבי כניסה ויציאה) ואחד בירך הימנית.
העברת העצמות להר הרצל.
גילוי השלד וזיהויו הוודאי עורר פולמוס באשר לשאלה היכן המקום המתאים לקברו. היו שטענו כי יפה וראוי לקברו היכן שנרצח, בחולות המדבר מדרום לרפיח. מנגד דרשו אנשים אחרים, ובהם ארוסתו של אבשלום, רבקה אהרנסון, כי יש לקבור את פיינברג בעתלית, שם פעל ועבד בשנותיו האחרונות. עיריות ראשון לציון וחדרה ומועצות זכרון יעקב וגדרה רצו שייקבר בשטחן, כי גם בהן חי במהלך חלקים מחייו. לבסוף הוחלט כי אבשלום פיינברג ייקבר, אחרי מסע שיעבור בראשון לציון, נס ציונה, רחובות וגדרה, בלוויה צבאית בחלקת עולי הגרדום בהר הרצל, בתאריך כ"ו בחשוון תשכ"ח, 29 בנובמבר 1967. שקיקי עפר מהמקומות האחרים שאליהם היה קשור הונחו על קברו, ואף ניטע לצידו חוטר מן הדקל שצמח מכיסו (חוטר נוסף ניטע במאי 2009 בחצר בית הוריו של אבשלום בחדרה).
אבשלום פיינברג נקבר בצמוד אל קברו של יוסף לישנסקי.
נציגים מהכנסת, מהממשלה ומבית הנשיא באו להשתתף בטקס הלוויה. יו"ר הכנסת קדיש לוז נשא נאום וכן הרב שלמה גורן.
בלוויה אמר הרב גורן:
השפעה.
מציאת שלדו של אבשלום גרמה להכרה רשמית של מדינת ישראל בארגון ניל"י. בלוויה הצבאית אמר יו"ר הכנסת קדיש לוז את הדברים הבאים:
הכרה זו המשיכה גם לאחר מכן, בין השאר כאשר הוענק עיטור לוחמי המדינה גם לאנשי ניל"י, וכן כאשר החלה מדינת ישראל לחלק, ב-1981, "אות ניל"י" לשרידי אנשי ניל"י ולבני משפחותיהם.