I have had success using the Lithuanian online phone book and cell phone book. I sent several letters and received replies from two families. I know for sure that I am not related to one family, but they are willing to help me in my research. Chances are I am related to the other family, but we don't know for sure. We keep in contact, exchanged Christmas cards and pictures. If nothing else, I have made new friends.
Richie has the links to the phone books on the home page. Its definitely worth the price of a $1.00+ (Ican't remember exactly how much it was) stamp. Good luck.
Also, I did the same thing with my Polish family. I have found my relatives (100% sure) and we correspond by email and telephone. Writing letters to the people with the surnames you are researching in a specific area, is the way to go.
I've been meaning to ask....how did you do 'the same thing with your Polish family'? Do you have a good URL for a Polish phone book? Can you search it just by name? My Polish research is even more problematic than my Lithuanian research!
I, too, used the Lithuanian phone book - suggestion came from Rich to whom I owe a big thank you! I sent out about 15 letters and had positive responses from my grandmother's family (that I didn't even know existed). I had the pleasure of meeting some cousins when I went to Lithuania last month and I've stuck up an ongoing correspondence with one set of cousins. Prior to my arriving in Lithuania they sent me maps, photos of churches, cemeteries, etc. so I felt like I was coming home. I think it helped that four generations of my grandmother's family lived in the Stakiai area, near Jurbarkas, and there were still quite a few left there. Did not have as much success with my grandfather's family from Kursenai area. I did get one response but they did not think they were related.
I have to say that nothing can equal the feeling of seeing family names in a cemetery, seeing churches and farms that you've only heard about - it was a wonderful experience!