Greetings from Sydney Australia!
Although I cannot help with birth records I can provide some more information about why people went to Ufa - my parents lived there until 1946 when they were repatriated to Poland and my brother was born there. I am currently researching how and why people went to Ufa and other towns in the Soviet interior.
1. When Hitler invaded Poland 1st September 1939 and Stalin invaded from the east on 17 September hundreds of thousands (not just Jews) fled east into the Soviet zone. This Zone was known as the Eastern borderlands and was basically made up of Belorus and Ukraine. The decision was made in a rush, panic was everywhere but the overriding thought was communism or fascism? Hitler or Stalin? In testimonies those who went east made comments such as:
a. There is plunder on the one hand and plunder on the other but the Russians plunder one as a citizen and a man while the Nazis plunder one as a Jew.
b. And so one moment decides a person's fate - one runs this way, the other that way and neither knows what the future holds in store. But what can the future hold for a Jew I ask? Here it is bad and there it's no good.
People went by any transport available but many on foot. Parents encouraged the young ones to go, families were broken up but ecpected to be reunited. More men than women went since they were in danger of being conscripted, Women wanted to stay with parents or didn't want to travel with little children. They often employed people smugglers to help them cross the rivers to get to the Soviet side. The two major cities they went to were Bialystok and Lwow which became intensely overcrowded with little work available.
2. Stalin immediately wanted to turn his new territories into extensions of the communist state. Permanent residents immediately became Soviet citizens and a chaotic process called "Sovietization" began. As well as severe economic consequences, the NKVD quickly began to identify class enemies and other undesirables who were then deported to the gulags or special settlements. The refugees who had fled to the Soviet zone were offered Soviet "passports". If they refused they were to be sent back to Poland - one of Stalin's ruses. They were in fact put on cattle trains for weeks and weeks and travelled deep into remote territories to liv and work in appalling conditions.
Becoming a citizen could also mean being conscripted into the Red Army and then be sent anywhere they were needed. Generally Jews were not considered to be good soldiers so when they were conscripted they were put into labour battalions rather than fight on the front. I believe this is what happened to my father and why he ended up in Ufa where he worked on the railways. He even received an invalid pension after his leg was injured in a railway accident. My mother also worked for the Red Army as a seamstress - her job was to sew the long Russian nightshirts worn by the officers.
3. When Hitler broke the Molotov-Ribbentrop pact in June 1941, more chaos ensued. Stalin ordered factories and war plants to be dismantled and put on trains to get them out of the hands of the Germans. He chose major centres such as Ufa where the factories and plants were rebuilt to provide machinery and vehicles for the war effort. He also evacuated betweeen 1 and 2 million civilians many of whom were needed to run the factories and work in them. Ufa was a particularly useful area - oilfields, railways, mines and a major waterway. So your relatives could have been caught up in these evacuations. I haven't ruled out the possibility that my parents were caught up in these evacuation also.
You say that your family were from Lwow originally but perhaps they were not Lwow born - perhaps they also fled to Lwow from Poland escaping Hitler. Even if they were Lwow natives they still might have taken the opportunity to escape the Nazi invasion.
The overwhelming tragedy of this story is that those Jews who had fled to the Soviet zone and were unable or unwilling to move further east in June 1941 were then subject to the brutal murders perpetrated in Belarus and Ukriane by the Einsatzgruppen. About 1 million Jews were murdered. The irony was that those who were deported to "Siberia" survived and formed the She'erit Hapletah or the surviving remnant of the Jews of POland. Although up to 30% perished in Siberia due to disease, hunger, hard labour and terrible weather, around 250,000 did ultimately survive and were repatriated to Poland mostly in 1946. Stalin did not set out intentionally to save these Jews - he was after all fairly anti-Semitic. It was more that he benignly accepted their presence and they were to come into good use post war (a completely different yet fascinating story).
This part of the Holocaust story has been largely neglected till recently - it's a story that fell through the cracks. Up till recently, a holocaust survivor was defined by being in a camp or in hiding or under false papers. People who "ran away" could not be classed as survivors. Historians have begun unravelling this extraordinary tale. It's a story that has many parts - a most fascinating one is about about when the refugees and deportees were amnestied and the all flocked to Central Asia where they spent years in Tashkent and Samarkand and other exotoc places.
It's a complex piece of history and has taken me along time and a lot of reading to unravel this geo-political tale. But I do hope this helps to explain part of the Lwow/Ufa story.