A rendőrség az Ugly Tuna bárban kezdte keresni Briant, ahol utoljára látták. Mivel a déli kampuszkapu környéke kissé lepusztult volt, és magas volt a bűnözési ráta, a bár biztonsági kamerákat szerelt fel. Átnézték a felvételeket, amelyeken Brain, Florence és Reed látható, amint hajnali 1:15-kor felmennek egy mozgólépcsőn a bár főbejáratához. Briant a bár előtt látták 1:55 körül, negyven perccel a belépés után, amint röviden beszélgetett két fiatal nővel és elköszönt. Eltűnt a kamera keresőjéből, és a bárba vezető lépcsőhöz ment, nyilvánvalóan azért, hogy visszamenjen befelé. A kamera azonban nem rögzítette, amint nem sokkal később, a bár bezárása után távozott.
A nyomozók rájöttek, hogy lehetséges, hogy a bárban átöltözött, vagy sapkát vett fel, és lehajtott fejjel megkerülte a kamerát, és eltakarta az arcát. A nyomozók úgy vélték, hogy a férfi a létesítmény egy másik ajtaján keresztül távozhatott. Ez az ajtó azonban csak szolgálati használatra volt fenntartva, a közönség nem használhatta, kivéve vészhelyzet esetén. A terület, ahová a kijárat ezután vezetett, egy építkezéshez vezetett, amelyen a rendőrök szerint nehéz volt átmenni normális állapotban, hogy ne mondjam, részeg állapotban, egy átmulatott éjszaka után.
Mivel Columbusban van a legtöbb biztonsági kamera Ohio városai közül, több, mint Clevelandben, Cincinnatiben és Toledóban együttvéve, a rendőrök más bárok felvételeit ellenőrizték, hátha ezek a kamerák meg tudják magyarázni, hogyan hagyta el Brian az ivóhelyet. Három másik közeli bár kameráinak felvételei azonban nem mutatták Brian nyomát.
A keresés az Ugly Tuna-tól kezdődött, a rendőrök, akiket néha rendőrkutyák kísértek, alaposan átnézték az utcát, szemeteseket vizsgáltak, és megkérdezték a lakosokat, hogy látták-e őt. Brian képét ábrázoló plakátokat és lapokat helyeztek el a városban, és a személyazonosság jeleként a jobb felső karján lévő tetoválásra hivatkoztak, amely a Pearl Jam zenekar Alive című kislemezének ikonját ábrázolta, amelynek rajongója volt. A rendőrség még arra is rábeszélte a várost, hogy engedjék be őket a csatornarendszerbe, és ott kutassanak. Hasznos információ nem került elő. Brian King Avenue-n lévő lakásánál a járműve még mindig kint parkolt. A lakásban pedig semmi sem tűnt rendellenesnek.
Miután a rendőrség a bártól mérföldekre, minden irányban átkutatta az épületet, a baleseten és a bűntényen kívül más lehetőségeket is mérlegelni kezdett. Mivel édesanyja nemrég halt meg, feltételezték, hogy ideiglenesen elutazott, hogy magányosan gyászoljon. Eltűnése azonban véglegesnek bizonyult. Önkéntes eltűnésének nem derült ki nyilvánvaló oka.
Azokat, akik látták Briant azon az éjszakán, beleértve az apját is, hazugságvizsgálatra kérték fel. Reed és Randy Shaffer átmentek a sajátjukon, ahogy mindenki más is, míg Florence visszautasította. A két nőt, akivel Briant utoljára látták beszélgetni, később azonosították. 2009-ben azt vallották, hogy nem kérték tőlük a poligráfos vizsgálatot.
Waggoner minden este lefekvés előtt felhívta Brian telefonját, jóval az eltűnés után. Általában üzeneteket hagyott a hangpostán, de egy szeptemberi éjszakán háromszor csörgött. “Folyamatosan hívogattam, hogy meghallgassam, egyszerűen azért, mert ez volt az egyik legjobb hang, amit valaha hallottam, még akkor is, ha senki sem vette fel” – írta a MySpace-oldalán. A Cingular, Brian vezeték nélküli szolgáltatója azt mondta, hogy amit Waggoner hallott, az egy számítógépes hiba miatt történhetett. A telefonról érkező pinget a Columbustól 23 km-re északnyugatra fekvő Hilliard egyik mobiltornyánál észlelték.
A rendőrség számos tippet kapott, amelyek közül egyik sem vezetett jelentős áttöréshez az ügyben. Még abban az évben egy cincinnati Pearl Jam-koncerten Eddie Vedder énekes a dalok között időt szakított arra, hogy tippeket kérjen Brian eltűnésével kapcsolatban, de ezek sem segítettek. A lehetséges észleléseket Michiganben, Texasban és még Svédországban is vizsgálták.
Randy Shaffer egyedül folytatta a fia keresését. Egy médium, akivel konzultált, azt mondta neki, hogy Brian holtteste a vízben van egy hídmóló közelében. Ő és Brian bátyja, Derek, valamint más polgárok, akik érdeklődtek az ügy iránt, gumicsizmát vásároltak, és szabadidejük nagy részét az Olentangy folyó partján töltötték, amely Columbuson keresztül folyik az egyetemi kampusz mellett, és hiába keresték a holttestet a hidak közelében. Ez a lehetőség arra is késztette a rendőrséget, hogy röviden fontolóra vegye a sokat vitatott elméletet, miszerint a gyilkosságot a Mosolygó Arc néven ismert sorozatgyilkos követte el. Brian Shaffer ezen elmélet szerint a gyilkos egyetlen olyan áldozata lenne, akinek a holttestét még nem találták meg. A Columbus rendőrség végül elutasított minden kapcsolatot a Brian ügyében feltételezett gyilkossal, követve a legtöbb bűnüldöző szerv, köztük az FBI nyomozását.
2008 szeptemberében, egy súlyos szélvihar idején Ohio középső részén Randy Shaffer, aki baltimore-i házának hátsó kertjében tartózkodott, meghalt egy ágtól, amely a szél erejétől letört és halálosan eltalálta. A szomszédok másnap reggel találták meg a holttestét, és hívták a rendőrséget.
A gyászjelentés online közzététele után részvétnyilvánítás jelent meg. Az egyik aláíráson ez állt: “Apának, szeretettel, Brian”, és az Amerikai Virgin-szigetekről származik. Ez azt sugallta, hogy Brian talán elhagyta Columbust, hogy máshol kezdjen új életet. A további nyomozás során azonban kiderült, hogy a feljegyzést egy Franklin megyei, nyilvánosan hozzáférhető számítógépről tették közzé, és hogy az csak egy vicc volt.