1. Dvorianskie Knigi.
For members of aristocratic families it is somewhat easier to trace their roots since there are "Dvoryanskie knigi"(Noblemen Books?) - lists of noble families of russian aristocracy (belarusan and polish included). There is Belarussian Nobility Association"Hodnasc'"(Post Office Box 212; Minsk - 102, a.c. 212; 220 102 Belarus) It's FEEFHS U.S. Representative is Mr. J. David Zincavage (JDZ1@Delphi.com).

2. Litouskiia Metryki.
Another source of ancient information are so called "Litouskiya Metryki"(Lithuanian metrics). These are dozens of books of taxes gathered in XV-XVII centuries. They have exact locations and designate amount of property of particular taxpayer all over the Grand Duche of Lithuania (most of north-west of Belarus is included). I have one volume in Polish here in the UVa library, so there is a chance that you can find part of it in your local university. Original documents are scattered anywgere between Russia, Poland, Lithuania and even Sweden. These 556 folliants are greatest belarusan and lithuanian historical treasure. Let's hope they will survive mindlessness of politicians and will be all reprinted.

3. Church Listings.
An extremely valuable source of information are church listings of people baptized, married and died. It is done both in Orthodox Church and in Catholic. In Orthodox church these lists are usually kept forever in the local church where they were done. That's why many of these lists perished during the World War II in fires. In Catholic churches there is a chance to find these lists both in local church and somewhere in Rome (my guess) since it is very centralized. I can only guess that in Jewish, Muslim, Protestant and Uniya Churches similar lists have been kept too.

4. Annual reconcilliation reports (Russian Empire).
One of the other sources is the annual list of persons that have been at reconcilliation in Orthodox Church. The church was obliged to submit this lists to Tzar's Jandarms(Police). They served as an indicator of loyalty of person :)

5. Registration agency - ZAGS.
During soviet times and now still all births, marriages and deaths are registrated by governmental organization - ZAGS. It stands for Registration of Acts of Civil Events. There was a big love for abbreviations in the beginning of Soviet Era, and I guess this one had still survived :)

6. State Archives.
Also there are republican, oblast's and regional archives, where all valuable historical information and documents are stored. Most of them have restricted access but I think now it shouldn't be as strict as before.

See here links to state Archives of Belarus

7. Directory Services.
In big cities like Minsk there are simply so called "Byuro Rozyska"- the search bureau- that would find you a person by name, and some other key info like previous address or previous phone.

8. Passport and "Propiska".
There is one more funny feature that you might not even understand: PROPISKA. Anyone living on the territory of ex-USSR has an official place of his/her permanent location ("Propiska"). This address is stated in the passport, since EVERYONE older 16 gets passport. All over ex-USSR militia departments(police, jandarms) have a special division - "Passportnyj stol"(passport table)- busy registrating people and validating "Propiska" of citizens. This police system is a rudiment of an old soviet era. It does help to fight crime but mostly it restricts the freedom of location. Thus "passport stol" is one of organization that can help with recent addresses. They have the data on permanent location of people for the last 20(?) years and after expiration of 20(?) years these data go to archives.