Isn't 'dzielnica' also a good translation for neighbourhood?
dzielnica = district, which is larger than a neighbourhood
You could also use ' w sąsiedztwie' , although pronunciation may be a problem. :)
Would saying "W okolicy szukamy sklepu" be awkward?
Yeah, awkward. "In the neighbourhood we are looking for a shop".