Politiet begyndte at lede efter Brian på Ugly Tuna, den bar, hvor han sidst var blevet set. Fordi området omkring South Campus Gateway var noget belastet med en høj kriminalitetsrate, havde baren installeret overvågningskameraer. De gennemgik optagelserne, hvor Brain, Florence og Reed kunne ses gå op ad en rulletrappe til barens hovedindgang kl. 1.15 om natten. Brian blev set uden for baren omkring kl. 13.55, 40 minutter efter at han var kommet ind, hvor han talte kort med to unge kvinder og sagde farvel. Han forsvandt fra kameraets søger og gik hen til trappen op til baren, tilsyneladende for at gå ind igen. Men kameraet optog ham ikke, da han kort efter forlod baren, da den lukkede.
Undersøgere indså, at det var muligt, at han kunne have skiftet tøj i baren eller have taget en kasket på og med hovedet nedad, have omgået kameraet og skjult sit ansigt. Efterforskerne mente, at han måske var gået ud gennem en anden dør i forretningen. Denne dør var imidlertid kun beregnet til tjenestebrug og måtte ikke bruges af offentligheden, undtagen i nødstilfælde. Området, som udgangen så førte til, var en byggeplads, som betjentene mente, at det var svært at gå igennem i normal tilstand, for ikke at sige i beruset tilstand efter en druknat.
Da Columbus har flest overvågningskameraer af alle byer i Ohio, flere end Cleveland, Cincinnati og Toledo tilsammen, tjekkede betjentene optagelser fra andre barer for at se, om disse kameraer kunne forklare, hvordan Brian havde forladt den drikkende bar. Imidlertid viste billeder fra kameraer på tre andre barer i nærheden ingen spor af Brian.
Søgningen begyndte at brede sig fra Ugly Tuna, og betjente, nogle gange ledsaget af politihunde, kiggede nøje på gaden, inspicerede skraldespande og spurgte beboerne, om de havde set ham. Plakater og sider med Brians billede blev hængt op rundt omkring i byen, og som et tegn på hans identitet nævnes en tatovering på hans højre overarm af ikonet fra singlen Alive fra bandet Pearl Jam, som han var fan af. Politiet overtalte endda byen til at lade dem gå ind i kloaksystemet og søge der. Der blev ikke fundet nogen nyttige oplysninger. I Brians lejlighed på King Avenue stod hans bil stadig parkeret udenfor. Og inde i lejligheden var der intet galt.
Efter at have ledt kilometer væk fra baren i alle retninger, begyndte politiet at overveje andre muligheder end en ulykke eller et uheld. Da hans mor for nylig var død, blev der spekuleret i, at han var rejst væk midlertidigt for at sørge i ensomhed. Det viste sig imidlertid, at hendes forsvinden var permanent. Der var ingen åbenlyse årsager til hans frivillige forsvinden.
De personer, der havde set Brian den aften, herunder hans far, blev bedt om at tage løgnedetektionstests. Reed og Randy Shaffer bestod deres, ligesom alle andre, mens Florence nægtede. De to kvinder, som Brian sidst blev set tale med, blev senere identificeret. De vidnede i 2009, at de ikke blev bedt om at tage en løgnedetektor.
Brian Shaffer efterlyste plakat.
Waggoner ringede til Brians telefon hver aften inden sengetid længe efter forsvindingen. Han plejede at lægge beskeder på telefonsvareren, men en aften i september ringede den tre gange. “Jeg blev ved med at ringe til den for at lytte til den, simpelthen fordi det var en af de bedste lyde, jeg nogensinde havde hørt, selv om ingen svarede,” skrev han på sin MySpace-side. Cingular, Brians trådløse udbyder, sagde, at det, som Waggoner hørte, kan have været en computerfejl. Et ping fra telefonen blev registreret ved en mobilmast i Hilliard, 23 km nordvest for Columbus.
Politiet modtog mange tip, men ingen af dem resulterede i større gennembrud i sagen. Ved en Pearl Jam-koncert senere samme år i Cincinnati tog sanger Eddie Vedder sig tid mellem sangene til at bede om tips om Brians forsvinden, men ingen af dem hjalp heller ikke. Mulige observationer i Michigan, Texas og endda i Sverige blev undersøgt.
Randy Shaffer fortsatte eftersøgningen af sin søn på egen hånd. En synsk person, som hun konsulterede, fortalte hende, at Brians lig lå i vandet nær en bropynt. Han og Brians bror Derek købte sammen med andre borgere, der havde interesseret sig for sagen, waders og tilbragte en stor del af deres fritid langs bredden af Olentangy-floden, der løber gennem Columbus ved siden af universitetsområdet, hvor de forgæves ledte efter liget nær broerne. Denne mulighed fik også politiet til kortvarigt at overveje den meget omdiskuterede teori om mord begået af den seriemorder, der er kendt som Smiley Face. Brian Shaffer ville ifølge denne teori være det eneste offer for morderen, hvis lig endnu ikke var blevet fundet. Politiet i Columbus afviste i sidste ende enhver forbindelse til den formodede morder i Brians sag og fulgte dermed de fleste retshåndhævende myndigheder, herunder FBI, der efterforskede ham.
I september 2008 blev Randy Shaffer, der befandt sig i baghaven i sit hjem i Baltimore, under en voldsom storm i det centrale Ohio dræbt af en gren, der knækkede af under vinden og ramte ham med døden til følge. Naboer fandt hans lig næste morgen og tilkaldte politiet.
Efter at hans nekrolog blev lagt ud på nettet, blev der offentliggjort et kondolenceafsnit. En af underskrifterne på det lød “To Dad, with love, Brian” og stammede fra De Amerikanske Jomfruøer. Det tydede på, at Brian måske havde forladt Columbus for at starte et nyt liv et andet sted. Ved en nærmere undersøgelse viste det sig imidlertid, at notatet var blevet sendt fra en offentligt tilgængelig computer i Franklin County, og at det blot var en joke.