I think, there is no an oficial phone/address base for people search, only for organization, but... try this site http://www.nomer.org/vladivostok/ .
For organizations - http://vladivostok.yell.ru/