The "Square Root" Solution of Oblivious RAM Simulation
Presumably, the shelter could store a bunch of pairs $(a,v)$ where $v$ is the contents of the virtual word at address $a$.  Then, to scan through the shelter to see whether it has the value of the virtual word at address $i$, you'd just check whether the shelter contains any pair $(a,v)$ where $a=i$.

I don't know whether this is actually what Goldreich and Ostrovsky do, but it seems like one natural candidate scheme that could be used.