Poliisi alkoi etsiä Briania Ugly Tuna -baarista, jossa hänet oli viimeksi nähty. Koska South Campus Gatewayn ympärillä sijaitseva alue oli jossain määrin rähjäinen ja rikollisuusaste oli korkea, baariin oli asennettu turvakamerat. He kävivät läpi kuvamateriaalin, jossa Brainin, Florencen ja Reedin nähtiin menevän liukuportaita ylös baarin pääsisäänkäynnille kello 1.15 yöllä. Brian nähtiin baarin ulkopuolella noin kello 13.55, neljäkymmentä minuuttia sisääntulon jälkeen, puhumassa lyhyesti kahden nuoren naisen kanssa ja hyvästelemässä. Hän katosi kameran etsimestä ja meni baariin johtaville portaille, ilmeisesti palatakseen takaisin sisälle. Kamera ei kuitenkaan tallentanut hänen poistumistaan pian sen jälkeen, kun baari sulkeutui.
Tutkijat ymmärsivät, että oli mahdollista, että hän olisi voinut vaihtaa vaatteita baarissa tai laittaa lippiksen päähänsä ja pää alaspäin laskeutuneena kiertää kameran ja peittää kasvonsa. Tutkijat arvelivat, että hän saattoi poistua laitoksen toisesta ovesta. Tämä ovi oli kuitenkin tarkoitettu vain palvelukäyttöön, eikä sitä saanut käyttää yleisö, paitsi hätätilanteissa. Alue, jonne uloskäynti sitten johti rakennustyömaalle, jonka läpi oli poliisien mielestä vaikea kävellä normaalitilassa, puhumattakaan humalassa ryyppyillasta poistumisen jälkeen.
Koska Columbuksessa on Ohiossa eniten valvontakameroita, enemmän kuin Clevelandissa, Cincinnatissa ja Toledossa yhteensä, poliisit tarkistivat muista baareista otettua kuvamateriaalia nähdäkseen, voisivatko nämä kamerat selittää sen, miten Brian oli lähtenyt ryyppyillallisesta baarista. Kolmen muun läheisen baarin kameroiden kuvissa ei kuitenkaan näkynyt jälkeäkään Brianista.
Etsinnät alkoivat levitä Ugly Tuna -ravintolasta, ja poliisit, joskus poliisikoirien saattelemina, tutkivat tarkkaan katuja, tarkastivat roskiksia ja kyselivät asukkailta, olivatko he nähneet häntä. Brianin kuvalla varustettuja julisteita ja sivuja oli esillä eri puolilla kaupunkia, ja hänen henkilöllisyytensä merkkinä mainittiin hänen oikeaan käsivarteensa tatuoitu Pearl Jam -yhtyeen, jonka fani hän oli, Alive-singlen kuvake. Poliisi jopa suostutteli kaupungin päästämään heidät viemäriverkkoon ja tekemään siellä etsintöjä. Mitään hyödyllistä tietoa ei löytynyt. Brianin asunnolla King Avenuella hänen autonsa oli yhä pysäköity ulkona. Asunnossa mikään ei näyttänyt olevan vialla.
Kun poliisi oli tutkinut kilometrien päässä baarista joka suuntaan, se alkoi harkita muitakin mahdollisuuksia kuin onnettomuutta tai rikollista peliä. Koska hänen äitinsä oli hiljattain kuollut, arveltiin, että hän oli lähtenyt väliaikaisesti suremaan yksinäisyyteen. Hänen katoamisensa osoittautui kuitenkin pysyväksi. Selviä syitä hänen vapaaehtoiselle katoamiselleen ei ilmennyt.
Niitä, jotka olivat nähneet Brianin sinä yönä, mukaan lukien hänen isänsä, pyydettiin tekemään valheenpaljastustestit. Reed ja Randy Shaffer läpäisivät omansa, kuten kaikki muutkin, kun taas Florence kieltäytyi. Kaksi naista, joiden kanssa Brianin nähtiin viimeksi puhuvan, tunnistettiin myöhemmin. He todistivat vuonna 2009, ettei heitä pyydetty valheenpaljastuskokeeseen.
Waggoner soitti Brianin puhelimeen joka ilta ennen nukkumaanmenoa vielä pitkään katoamisen jälkeen. Hän jätti yleensä viestejä vastaajaan, mutta eräänä syyskuun iltana se soi kolme kertaa. ”Jatkoin soittamista kuunnellakseni sitä yksinkertaisesti siksi, että se oli yksi parhaista äänistä, joita olin koskaan kuullut, vaikka kukaan ei vastannut”, hän kirjoitti MySpace-sivullaan. Cingular, Brianin langattoman verkon tarjoaja, sanoi, että Waggonerin kuulema saattoi johtua tietokonehäiriöstä. Puhelimen pingaus havaittiin matkapuhelinmastossa Hilliardissa, 23 kilometriä Columbuksesta luoteeseen.
Poliisi sai useita vihjeitä, joista yksikään ei johtanut merkittäviin läpimurtoihin tapauksessa. Pearl Jamin konsertissa myöhemmin samana vuonna Cincinnatissa laulaja Eddie Vedder pyysi kappaleiden välissä vinkkejä Brianin katoamisesta, mutta niistäkään ei ollut apua. Mahdollisia havaintoja Michiganissa, Texasissa ja jopa Ruotsissa tutkittiin.
Randy Shaffer jatkoi poikansa etsintöjä yksin. Selvänäkijä, jota hän konsultoi, kertoi hänelle, että Brianin ruumis oli vedessä lähellä sillan laituria. Hän ja Brianin veli Derek sekä muut tapauksesta kiinnostuneet kansalaiset ostivat kahluuhousuja ja viettivät suuren osan vapaa-ajastaan Columbuksen läpi virtaavan Olentangy-joen rannoilla yliopiston kampuksen vieressä etsien turhaan ruumista siltojen läheltä. Tämä mahdollisuus sai poliisin harkitsemaan lyhyesti myös paljon keskustelua herättänyttä teoriaa Hymynaamana tunnetun sarjamurhaajan tekemästä murhasta. Brian Shaffer olisi tämän teorian mukaan ainoa murhaajan uhri, jonka ruumista ei ole vielä löydetty. Columbuksen poliisi hylkäsi lopulta kaikenlaisen yhteyden Brianin tapauksen epäiltyyn tappajaan ja seurasi useimpien häntä tutkineiden lainvalvontaviranomaisten, myös FBI:n, esimerkkiä.
Syyskuussa 2008 keskisessä Ohion osavaltiossa puhjenneen voimakkaan myrskytuulen aikana baltimorelaisen kotitalonsa takapihalla ollut Randy Shaffer kuoli oksaan, joka katkesi tuulen voimasta ja osui häneen kuolettavasti. Naapurit löysivät hänen ruumiinsa seuraavana aamuna ja soittivat poliisille.
Kun hänen muistokirjoituksensa julkaistiin verkossa, julkaistiin surunvalitteluosio. Yhdessä allekirjoituksessa luki ”Isälle, rakkaudella, Brian”, ja se oli peräisin Yhdysvaltain Neitsytsaarilta. Tämä viittasi siihen, että Brian oli saattanut lähteä Columbuksesta uuden elämän perässä muualle. Tarkemmissa tutkimuksissa kävi kuitenkin ilmi, että viesti oli lähetetty Franklinin piirikunnan julkisesti saatavilla olevalta tietokoneelta ja että se oli vain vitsi.