בספטמבר 1999 היו מספר מתקפות טרור במוסקבה ובערים אחרות ברוסיה. מספר בניינים פוצצו ובני אדם רבים נהרגו. הקרמלין טען שבדלנים צ'צ'נים היו אחראיים לפיגועים. באותה תקופה קבוצה של שכנים המתגוררים בבניין דירות מצאו כמות גדולה של חומרי נפץ במרתף של הבניין שלהם ודיווחו על כך לשירות הביטחון הפדרלי. באותו זמן קבוצה של עיתונאים חוקרים עצמאיים חשפו עובדות מסוימות שקישרו בין הפיצוצים לאנשים הקשורים לשירות הביטחון הפדרלי. ערוץ NTV של גוסינסקי החליט לנקוט בגישה עצמאית ופתח בחקירה עיתונאית ציבורית מעמיקה - וחקר את האפשרות ששירות הביטחון הפדרלי ביים את הפיצוצים על מנת להשפיע על הבחירות הקרובות. העובדה שערוץ NTV של גוסינסקי פתח בחקירה עוררה זעם בקרמלין, ולמעשה, לגוסינסקי ניתן אולטימטום להוריד את "החקירה העצמאית" מ-NTV, או להתמודד עם ההשלכות - גוסינסקי סירב. יתרה מזאת, מספר פרשנים עצמאיים האשימו את הקרמלין ואת פוטין בארגון הפיצוצים, מה שהוביל למלחמה חדשה בצ'צ'ניה, כאשר המטרה הייתה להגביר את הפופולריות של פוטין לקראת הבחירות. הייתה זו נקודת השבירה במערכת היחסים בין גוסינסקי והקרמלין, המשפחה, ויורשו של ילצין, פוטין.
בינואר, גוסינסקי נבחר לסגן נשיא הקונגרס היהודי העולמי. לאחר שהתפטרותו של ילצין הפכה את פוטין לנשיא בפועל, והבחירות שנערכו בהמשך במאי 2000 העלו את פוטין לשלטון, אחת מהפעולות מעוררות המחלוקת הציבורית הראשונות של הנשיא החדש פוטין - נפתחה חקירה נגד גוסינסקי במטרה לאפשר לממשלה להשתלט על NTV ולהשתיק את האופוזיציה.
ביוני אותה שנה, משרד התובע הכללי פתח בחקירה נגד גוסינסקי על מעילה בכספים עם חברה בשם "Russian video". ב-13 ביוני הוא נעצר במוסקבה ונכלא בכלא בוטירקה הידוע לשמצה. זמן קצר לאחר מעצרו, נציגים מהקרמלין הציעו לגוסינסקי למכור את מדיה מוסט ב-300 מיליון דולר בתמורה לשחרורו. הצעה זו התפרסמה בהמשך בתור עסקת ״מניות תמורת חירות״ או פרוטוקול מס 6 והייתה חתומה על ידי השר לסין בתפקידו.
העסקה גרמה לשערורייה ציבורית גדולה, יום לאחר מעצרו של גוסינסקי ב-14 ביוני, נשיא ארצות הברית קלינטון נשאל במסיבת עיתונאים לדעתו בנוגע למעצרו של גוסינסקי, והוא השיב שהוא לא חושב שזה ראוי לעצור אנשים על השמעת ביקורת על הקרמלין, יתרה מזאת, פוטין, שביקר בספרד בעת המעצר נאלץ לענות על שאלות בנושא. אחת מהתשובות של פוטין הייתה "אני לא יודע על זה שום דבר, ואיני יכול ליצור קשר עם התובע הכללי של רוסיה". כעבור שלושה ימים ובעקבות לחץ ציבורי אדיר, השערורייה, והספקולציות, ב-16 ביוני, גוסינסקי שוחרר מהכלא והושם במעצר בית. מספר שבועות לאחר מכן, ביולי, הוא חתם על הסכם במסגרתו מכר את כל נכסי התקשורת תמורת 300 מיליון דולרים. החקירה הפלילית נסגרה, ומיד לאחר מכן גוסינסקי עזב את רוסיה. מאותו היום גוסינסקי לא חזר לרוסיה.
בנסיעתו האחרונה לשדה תעופה של מוסקבה, ליווה אותו בוריס נמצוב, מנהיג האופוזיציה שחוסל בפברואר 2015 בסמוך לקרמלין. מחוץ לרוסיה, גוסינסקי התכחש לעסקה וטען שהיא נחתמה תחת איומים. זמן קצר לאחר שגוסינסקי עזב את רוסיה, מנכ״ל גזפרום מדיה אלפרד קוך, פנה לתובע הכללי של רוסיה בבקשה לפתוח בחקירה חדשה נגד גוסינסקי ומדיה מוסט, בטענה על שימוש לא הולם בערובות של גזפרום לקבלת אשראי (באותה תקופה גזפרום החזיקה ב-12.5% ממניות מדיה מוסט ו-30% ממניות NTV). משרד התובע הכללי הגיש בקשה למשרד הראשי של האינטרפול בליון להוצאת צו מעצר בינלאומי במטרה לעצור ולהסגיר את גוסינסקי. המשרד הראשי של אינטרפול דחה את הבקשה הרוסית וביקש להבהיר את הסיבה על מנת למנוע הפרה של אמנת אינטרפול, האוסרת על התערבות בנושאים פוליטיים. לבסוף באינטרפול סירבו בתוקף להוציא כל צו מעצר נגד גוסינסקי, וכשהרשויות ברוסיה ערערו על הסירוב, מטה אינטרפול תמך בתוקף בסירוב.
ב-17 בנובמבר מדיה מוסט חתמה על הסכם פשרה עבור הערובות של גזפרום ועבור התחייבויות קיימות ועתידיות (שהבשילו בשנת 2001). מיד לאחר החתימה על הסכם הפשרה, אלפרד קוך מגזפרום מדיה כתב לתובע הכללי והודיע לו שהסכם הפשרה בוצע בהצלחה והודה לו על עזרתו. על אף שהסכם פשרה זה נחתם על ידי גוסינסקי תחת איומים של מעצר והסגרה, גזפרום הודתה ששווי הנכסים של מדיה מוסט הוערך בסכום של יותר מ-1.1 מיליארד דולר. עם זאת, הסניף הרוסי של אינטרפול התעלם מהסכם הפשרה, ומסירוב המשרד הראש של אינטרפול להוציא צו מעצר בינלאומי (לאור החשד שהמעצר נגוע במניעים פוליטיים), עקף את הסירוב של המשרד הראשי, פנה ישירות לסניף הספרדי של אינטרפול וביקש לעצור ולהסגיר את גוסינסקי. ב-12 בדצמבר גוסינסקי נעצר בספרד על סמך הבקשה הרוסית. צו המעצר הוצא על ידי השופט בלתאסאר גארסון. ב-22 בדצמבר, השופט גארסון שחרר את גוסינסקי מהכלא והעביר אותו למעצר בית בביתו של גוסינסקי בדרום ספרד. ההחלטה לשחרר את גוסינסקי התקבלה בביקורת חריפה בספרד, ומשרד התובע ערער עליה, מכיוון שהיה זה לא מקובל לשחרר זר העומד בפני הסגרה ולהכניסו למעצר בית.
בינואר 2001 גוסינסקי הגיש תביעה נגד רוסיה לבית המשפט האירופי לזכויות אדם על הפרת הזכויות והחירויות שלו. באפריל, בית המשפט הלאומי של ספרד דחה את בקשת הפדרציה הרוסית להסגרתו של גוסינסקי. בית המשפט הספרדי ציין כי האישומים נגד גוסינסקי היו נגועים במניעים פוליטיים ושלמעשה הוא אפילו לא ביצע שום פשע - בית המשפט הלאומי ציין במיוחד כי "ניתן לראות במסמכים שהוגשו על ידי [המבקש] ..." נסיבות בולטות ומשונות במיוחד שאינן אופייניות בתביעות המשפטיות בתחום ההונאה, ושאף על פי שאינן מובילות בעצמן למסקנה שאנו עוסקים בתביעה לא שגרתית שהוגשה למטרה פוליטית, הן מחייבות את בית המשפט לשקול שהטיעון [של המבקש] אינו חסר ביסוס באופן מוחלט בכל הנוגע לעובדות ולהתערבויות ואין זה בלתי מתקבל על הדעת או מופרך על בסיס קריטריונים של הגיון והניסיון." גוסינסקי זוכה.
באמצע אפריל, הפדרציה הרוסית פשטה על המשרדים של מדיה מוסט ו-NTV. מספר ימים בלבד לאחר שבית המשפט הלאומי של ספרד קבע כי האישומים נגד גוסינסקי נגועים במניעים פוליטיים ואינם מהווים פשע, הפדרציה הרוסית פתחה בהליכים פליליים חדשים נגד גוסינסקי והוציאה צו מעצר חדש, עם טענות של הלבנת כספים שבבעלותם גזפרום. ממשלת הפדרציה הרוסית הגישה בפעם נוספת בקשה למעצרו של גוסינסקי בביתו בספרד, אך גוסינסקי לא היה שם - הוא נסע לישראל. מספר חודשים לאחר מכן בית המשפט הלאומי דחה את הבקשה החדשה של שלטונות רוסיה וטען שהיא חסרת בסיס. ביולי ועד הפיקוח של אינטרפול המליץ לעצור כל פעולה עתידית נגד גוסינסקי על בסיס בקשות הפדרציה הרוסית. מזכ״ל אינטרפול, רונלד נובל, תיאר את התביעה נגד גוסינסקי כ-"בעלת אופי פוליטי מובהק". באוגוסט, ישראל סרבה להסגיר את גוסינסקי לרוסיה.
במאי 2002, גוסינסקי השיק פרויקט טלוויזיה חדש - RTVI או RTVI International, שהמשיך את מה ש-NTV International התחיל - שידור חדשות אובייקטיביות ברוסית לדוברי רוסית ברחבי העולם. באוקטובר, פרויקט האינטרנט החדש של גוסינסקי, Newsru.com, התחיל לפעול מכתובתו החדשה. לפני כן הפרויקט פעל כ-NTV.ru, אך שם הדומיין הזה ניתן לגזפרום מדיה, הבעלים החדשים של NTV. העיצוב של האתר נוצר על ידי המעצב הבינלאומי הנודע סמיון לוין. Newsru.com כלל את המקור האינטרנטי נושא השבחים Inopressa.ru - המספר תקצירים של החדשות היומיות מהעיתונות המודפסות הזרה בתרגום לרוסית. כיום, לאתר Newsru.com יש מעל ל-65 מיליון דפים נצפים ו-7.5 מיליון מבקרים יוניקים מדי חודש.
באוגוסט 2003, גוסינסקי נעצר ביוון בעקבות בקשת ההסגרה נוספת מהפדרציה הרוסית. כעבור מספר ימים הוא שוחרר בערבות והמתין להחלטה תוך שהוא מתחייב לא לעזוב את אתונה. שלושה חודשים לאחר מכן, בעודו ממתין להחלטת בית המשפט היווני בנוגע להסגרתו, חדר המלון של גוסינסקי נפרץ בזמן ששהה במסעדה. עלו טענות שמדובר בפריצה מקצועית אך המשטרה סרבה להגיב בנוגע לפריטים שנגנבו. באוקטובר, לאחר שבחן את הטענות שהועלו נגד גוסינסקי על ידי הפדרציה הרוסית, בית המשפט לערעורים באתונה דחה את בקשת ההסגרה. בית המשפט לערעורים קבע שהמעשים שהיו מיוחסים לגוסינסקי לא נוגדים את החוק היווני.
במאי 2004, בית המשפט האירופי לזכויות אדם קבע שהמעצר והאישומים הפליליים נגד גוסינסקי הפרו את סעיף 5 וסעיף 18 של האמנה להגנה על זכויות אדם וחירויות יסוד, תוך ציון שהעובדות עליהן מבוססת התביעה נגד גוסינסקי ברוסיה היו נגועות במניעים פוליטיים ונועדו לאיים עליו. הפדרציה הרוסית ערערה. בנובמבר, בית המשפט האירופי לזכויות אדם דחה את הבקשה של הפדרציה הרוסית לשקול מחדש את החלטתו.
גוסינסקי איחד את פעילויות הפקת הטלוויזיה שלו לתוך חברת החזקות החדשה הנקראת New Media Distribution Company. החברה הפכה לאחת מהמפיקות הגדולות ביותר של דרמות מקוריות המשודרות בפריים טיים בשפה הרוסית, ומכרה את הפקותיה למספר רשתות שידור רוסיות, לרבות NTV ו-RTR, וכן לערוצי שידור אחרים באזורים דוברי רוסית אחרים בעולם (או בכל מקום שבו נפוצה השפה הרוסית). בעשור האחרון NMDC הפיקה מעל ל-3,000 פרקים מקוריים, כשרבים מהם זכו לפרסום ומשכו אחוזי צפייה גבוהים. NMDC גם מחזיקה במספר ערוצי טלוויזיה ייעודיים בתשלום, לרבות Detskii Mir (עולם הילדים), Teleclub ,Nashe kino (הסרטים שלנו) ו-Mir Seriala (עולם הסדרות). המשרדים הראשיים של NMDC יושבים בג'ורג'טאון שבאיי קיימן והחברה מפעילה חברת בת ברוסיה ובמספר מדינות נוספות באירופה.