משרד הפנים החליט לבחון מחדש את האזרחות הישראלית של צ'רנוי
בשנת 1999 הוחרם דרכונו של צ'רנוי ובמקומה הונפקה לו תעודת מעבר. שר הפנים הבא אמור להכריע אם תושב לו אזרחותו
מאוחר יותר הדרכון נמצא, אולם מששב צ'רנוי לישראל דרכונו הוחרם במעבר הגבול ובמקומו הונפקה לו תעודת מעבר. כחודש לאחר מכן קיבל עורך דינו של צ'רנוי, שדרש להבין מדוע נלקח הדרכון, מכתב בזו הלשון: "בירור יסודי שקיימנו העלה כי יש ספק אם מרשך היה זכאי מלכתחילה לקבל דרכון ישראלי. . . בעקבות מידע שנמסר לנו ממשטרת ישראל, עולה חשד לפיו לכאורה השיג מרשך את האזרחות הישראלית שלא כדין".
מאז משקיע צ'רנוי מאמצים אדירים בקבלת הדרכון חזרה. עשרות מכתבים נשלחו לשרי הפנים השונים וגם חברי כנסת וראש ממשלה אחד - אריאל שרון - קיבלו פניות בנושא.
בשנת 2005 קיבל צ'רנוי מכתב תגובה משר הפנים דאז, אופיר פינס, בו לראשונה הופיע פירוט החשדות נגדו: "המידע שהגיע למשטרת ישראל מלמד על מעורבות של צ'רנוי בשורה של מעשי רצח, ניסיון לרצח, אלימות ואיומים על רקע 'מלחמות האלומיניום'.
"באופן פרטני ניתן לציין מידע המלמד על מעורבותו לכאורה במעשי רצח שבוצעו בין השנים 93'-95' של הנרצחים הבאים: איגור בלנצקי, יורי קרטניקוב, אלכסנדר בוריסוב, פליקס לבוב וואדים יפסוב. כן קיים מידע על מעורבותו בקשירת קשר לרציחתו של איוואן טורישב... לפי המידע שהובא בפניי, מעשי הרצח והאלימות הוצאו לפועל, בעיקרם, באמצעות ארגון הפשע איסמעילובה, בראשותו של אנטון מאלבסקי.
"החשדות בנושא הלבנת הון מתייחסים לחשדות להלבנה
של מיליוני דולרים. עבירות המקור הן עבירות מרמה והונאה שבוצעו ברוסיה בתחילת שנות ה-90. מעבר לכך לא נוכל לפרט".
עוד מתייחס המכתב לקשרים לכאורה של צ'רנוי עם ארגון הפשע איסמעילובה, "עם בכירי הפשיעה המאורגנת באוזבקיסטן, ובראשם גאפור רחימוב וסלים עבדולייב, ועם ארגון סולנצבו, בראשות סרגיי מיכאלוב.
לפי המידע, הקשר עם ארגון איסמעילובה התבטא בעיקר בכך שאנשי הארגון ביצעו עבירות כגון איומים, אלימות ורצח להשגת מטרות שמרשכם מעוניין היה להשיג, ובהן השתלטות על מפעלי אלומיניום".
כשנה לאחר מכן מינה שר הפנים פינס את יצחק ענבר לעמוד בראשות ועדת יחיד שתבחן את שאלת אזרחותו הישראלית של צ'רנוי. עוד בטרם התקבלה ההמלצה הגישו עורכי דינו של צ'רנוי עתירה לבג"ץ נגד משרד הפנים, בגין "מסע הייסורים", כהגדרתם, שנכפה על מרשם.
בעתירה מובאות עשרות עדויות של פקידים ואנשי אכיפת חוק רוסים, שמעידים כי נגד צ'רנוי מעולם לא נפתחו תיק פלילי או חקירה בדבר ההאשמות שהציג משרד הפנים. לגבי מכריו, כותבים עורכי הדין: "מן הראוי לציין כי חלק מהאנשים ששמם צוין... הם חברי ילדות של מר צ'רנוי שגדלו עימו בעיר טשקנט שבאוזבקיסטן; ואילו חלקם מוכר לו מפעילותו כספונסר לקידום תחרויות ספורט... מר צ'רנוי אינו אחראי למעשיהם של אנשים אלה בתחומים אחרים של חייהם".
בנובמבר 2008 נזף בג"ץ במדינה על הסחבת בעניינו של צ'רנוי. במסגרת העתירה הוסכם בין הצדדים כי צ'רנוי יקבל חזרה את דרכונו לשנה, עד לקבלת החלטה סופית בעניינו. סבין חדד, דוברת מינהל האוכלוסין, מסרה בתגובה: "הנושא עדיין בטיפול והוא יונח על שולחנו של שר הפנים הבא".