The problem is that registration of a foreigner is somewhat long and bureaucratic procedure and almost none of people who would want to rent their flats would want to go through that procedure. And most of them haven't had any previous experience with it. Also such people usually rent for cache, which means they do it unofficially and most likely don't pay taxes from it and they would be reluctant to meet authorities. In other words why go through all these troubles if there are Russians who would want to rent too.
BTW if you don' have a registration in 7 days after crossing the border - you would be breaking a law.
In my opinion you should have a place to stay and already prepared before you go. Somebody should be ready to go through all these troubles before you cross the border, listen to Mary, she has good points.