No, you can actually get 3 months double entry without having been to Russia before.
Then there are sometimes agencies that can get you like 12 months multiple entry the first time. However this is probably not so relevant for you as 3 months double entry seems enough for you.
What you have to know is that you might run into trouble at the border. And it seems to be mostly at the border from Russian Altai into Mongolia, what I heard from others and experienced myself.
Wr got questions about using business visa and we came up with a story about making a documentary. He still said it was wrong, but then we could bend the conversation a little bit as we could blame it on the visa agency that we used (but we did not name them). He was actually mentioning that we should have another visa, something like a cultural visa. Maybe it is the same that you were told.
You could get a fine or be expelled from the country or something like this.
So many people are advising to use a business visa and are doing that, but I just wanted to say it is not risk free.
Unfortunately it looks like UK citizines cannot get another Tourist visa in Ulaambatar. For us this worked quite well being Dutch.
And I don't think it is allowed to have two active visas, like if you would have a transit visa and a tourist visa in your passport.
Greetings from Japan as we did largely the same route. But we used our first double entry visa entering already in West Russia, and then in Altai again. Then we got a tourist visa in Ulaanbataar.
Getting a Transit visa in Ulaanbataar is not very nice to.go to Vladivostok. However we have seen some fast bikers do it.
Not sure how fast you are. You vould also look into double entry 30 days tourist visa if you are really racing it like some bikers do