La 9 iunie 2005, Van der Sloot și frații Kalpoe au fost arestați sub suspiciunea de răpire și ucidere a lui Holloway. Legislația din Aruba permite arestarea pe baza unor suspiciuni serioase din partea anchetatorilor; pentru a continua să se mențină suspectul în custodie, trebuie să se îndeplinească o sarcină probatorie din ce în ce mai mare la revizuirile periodice. Potrivit lui Dompig, accentul a fost pus de la "început" pe acești trei suspecți. Dompig a declarat că supravegherea celor trei a început la trei zile după ce a fost raportată dispariția lui Holloway și a inclus supravegherea, interceptări telefonice și chiar monitorizarea e-mailurilor acestora. Dompig a precizat că presiunea exercitată de familia lui Holloway i-a determinat să oprească prematur supravegherea și să îi rețină pe cei trei suspecți. Luni, 4 iulie, în urma audierilor în fața unui judecător, Deepak și Satish Kalpoe au fost eliberați, însă Joran van der Sloot a fost reținut pentru încă 60 de zile.
La 15 aprilie 2006, Geoffrey von Cromvoirt a fost arestat de autoritățile din Aruba, fiind suspectat de infracțiuni legate de traficul ilegal de stupefiante care, potrivit procurorului, ar fi putut avea legătură cu dispariția lui Holloway. La prima sa înfățișare în fața instanței, detenția sa a fost prelungită cu opt zile. Cu toate acestea, Von Cromvoirt a fost eliberat la 25 aprilie 2006. În plus, un alt individ cu inițialele "A.B." a fost arestat la 22 aprilie 2006, dar a fost eliberat în aceeași zi.
La 17 mai 2006, un alt suspect, Guido Wever, fiul unui fost politician din Aruba, a fost reținut în Țările de Jos, fiind suspectat că a participat la răpirea, lovirea și uciderea lui Holloway. Wever a fost interogat timp de șase zile la Utrecht. Deși, inițial, procurorii din Aruba au încercat să obțină transferul său pe insulă, acesta a fost în schimb eliberat în urma unui acord între procuror și avocatul lui Wever.
Anchetatorii din Aruba au invocat ceea ce a fost descris ca fiind probe nou descoperite, Joran van der Sloot și Satish și Deepak Kalpoe au fost arestați din nou la 21 noiembrie 2007, fiind suspectați de implicare în "omor prin imprudență și vătămare corporală gravă care a dus la moartea lui Holloway". Van der Sloot a fost reținut de autoritățile olandeze în Olanda, în timp ce frații Kalpoe au fost reținuți amândoi în Aruba. Van der Sloot s-a întors ulterior în Aruba și a fost încarcerat.
În noiembrie 2007, Dave Holloway a anunțat o nouă acțiune de căutare a fiicei sale, prin care se va sonda marea dincolo de adâncimea inițială de 100 m, la care au avut loc căutările anterioare. Aceste căutări, la care a participat o navă numită Persistence, au fost abandonate din lipsă de fonduri la sfârșitul lunii februarie 2008, fără să se găsească nimic semnificativ.
La 30 noiembrie 2007, un judecător a ordonat eliberarea lui Satish și Deepak Kalpoe, în ciuda încercărilor procuraturii de a le prelungi detenția. Cei doi frați au fost eliberați în ziua următoare. Acuzarea a făcut apel împotriva eliberării fraților Kalpoe. Acest apel a fost respins la 5 decembrie 2007, instanța scriind: "În ciuda investigațiilor costisitoare și îndelungate privind dispariția ei și a persoanelor care ar putea fi implicate, dosarul împotriva suspectului nu conține indicii directe că Natalee a murit din cauza unei crime violente". Van der Sloot a fost eliberat fără acuzații la 7 decembrie 2007, din cauza lipsei de probe care să-l implice, precum și a lipsei de dovezi că Holloway a murit în urma unei infracțiuni violente. Procuratura a indicat că nu va face apel.
La 18 decembrie 2007, procurorul Hans Mos a declarat oficial cazul închis și a declarat că nu vor fi formulate acuzații din lipsă de probe. Acuzarea a indicat că este în continuare interesată de soții Kalpoe și de Joran van der Sloot (deși aceștia nu mai sunt acum suspecți din punct de vedere legal) și a susținut că unul dintre cei trei, într-un mesaj pe o cameră de chat, a declarat că Holloway era moartă. Acest lucru a fost contestat vehement de avocatul lui Deepak Kalpoe, care a declarat că acuzarea, în traducerea din papiamento în olandeză, a interpretat greșit o referire la un profesor care s-a înecat ca fiind o referire la Holloway. Avocatul Ronald Wix a mai declarat: "Dacă (Mos) nu găsește un cadavru în baia unuia dintre acești copii, nu mai au cum să-i aresteze".