ארגון עדאלה פנה ב-10 בינואר אל פרקליטות המדינה וביקש כי יינקטו הליכים פליליים נגד האחראים לפעולות הריסת הבתים הנרחבות שביצע כוחות צה"ל בדרום רצועת עזה במאי 2004, בעת מבצע "קשת בענן". עדאלה, באמצעות עו"ד מרואן דלאל, ביקש כי תיפתח חקירה פלילית נגד מי שפיקד על מבצע זה, תא"ל (מיל') שמואל זכאי, ונגד כל חייל או קצין אחר שהיה מעורב בפעולות הריסת הבתים.

במאי 2004 (24.5.2004-17.5.2004) יצא הצבא לפעילות צבאית בדרום רצועת עזה, במבצע שכונה "קשת בענן". במבצע זה נהרסו בתים רבים של פלסטינים המתגוררים באותו אזור. העיתונאי שלומי אלדר, שראה במו עיניו את פעולות הריסת הבתים שננקטו במבצע, תיעד אותן בספרו עזה כמוות:

"בכל מהלך המבצע שהיתי בשכונות שלאורך ציר פילדלפי. ראיתי אנשים נמלטים מבתיהם רגע לפני שהגיעו הדחפורים. הדי-9 המאיים, כמו מפלצת אדירה ורעבה, נסע וגרף שורות שורות של בתים בכפותיו. נשים וגברים רצו כאחוזי אמוק. ביד אחת החזיקו תינוק או ילד קטן שלא עמד בקצב המנוסה, וביד האחרת נשאו תיק שארזו במהירות לפני שברחו מאימת הדחפור. ליד אחת השוחות שנחפרו עמדה משפחה – אבא, אמא וכנראה גם סבא וסבתא – וקראו לילד שפיגר מאחור לחצות את השוחה. הילד פחד. הוא טמן את ראשו מאחורי תלולית עפר וסירב לעבור".

לבקשת עדאלה צורף דו"ח שכתב הדווח המיוחד מטעם האו"ם לענייני זכויות האדם בשטחים הכבושים, פרופסור ג'ון דוגארד, ב-12.8.2004. פרופסור דוגארד ביקר בזירת הפעילות של הצבא זמן קצר לאחר סיום מבצע "קשת בענן", והגיע למסקנה כי צה"ל הרס ו/או גרם נזק בלתי הפיך ל-167 בתים, שאיכלסו 379 משפחות המונות 2,066 נפשות. עדאלה גם צירף לבקשה דו"ח מקיף של ארגון זכויות האדם הבינלאומי Human Rights Watch, שכותרתו “Razing Rafah: Mass Home Demolitions in the Gaza Strip”. לפי דו"ח זה, שפורסם ב-18 באוקטובר 2004, הריסת הבתים הנרחבת במבצע "קשת בענן" היתה מהלך רצוני ומכוון, ולא חלק מהלחימה או ניסיון לתת מענה לצרכים צבאיים.

עדאלה צירף לבקשה גם עדויות של חיילים שהשתתפו במבצע "קשת בענן", שפורסמו ב"הארץ" ב-24 בינואר 2005 וב-15 במארס 2005. החיילים אמרו בעדויותיהם כי מבצע "קשת בענן" לווה ב"אווירה של הרס בלתי מרוסן" וכי אחד הקצינים אמר בסיכום המבצע: "כל הכבוד. הוכחתם שצה"ל יודע להיות צבא אכזרי".