First, please let's not waste anyone's energy by arguing over the semantics that you do not "register your visa" and instead this is a migration registration as some of you may be tempted to do. I'll continue to call it visa registration since we all know what it means.
Second, my understanding is you should register within 7 days upon arriving in Russia. You don't get another 7 days every time you move to another city! On the other hand as others have pointed out, the law is not clear here. You should keep in mind that the law in Russia is whoever the official confronting you says unless of course it is escalated to the court of law where you have legal representation to argue the text of the law in front of a judge! Please let's try not to go that far... I once visited a remote Russian town on the Far East with 300 fellow travelers. The Russian immigration descended at our hotel one day to round us up accusing us for entering a "special" region of Russia without a "special" permit, ie. our Russian visa was NOT good enough! They eventually let us go after scaring some of us to sign an apology letter. It was completely baseless and meant to show us they didn't welcome so many foreigners visiting their small world all at once.
When I traveled to Russia (physically been to all 11 time zones of Russia over the years), I have often stayed at my friend's apartments. Unfortunately, my friend's household registration (propiska) is at another region of the country. This means I can't register at a local post office or immigration authority with my friend as my host. In theory the landlord should register me. However, asking a landlord who has never done this before is more troubles than you might think. In a country where the government is not seen as public servants, people often rather avoid going to the government unless they have to.
I twice tried to register my visa by staying at a hotel for one night. However, they both declined my request citing they wouldn't register a guest staying for less than 3 days! These were actually well known western hotels like Radisson and Ramada in Moscow! When I challenged them with a situation of what if I travel from city to city and never stay at a place for more than 3 days, would I not get into trouble by their refusal to register me. The staff simply brushed me off by saying they wouldn't know what to do with a special situation like this and advised me to keep my hotel receipt as proof if I am ever confronted by an official. I reported the behaviors of Radisson and Ramada to the U.S. embassy, who confirmed both hotels violating the law and would further report it to the Russian authority. I don't know if anything tangible actually came out of it though.
My standard approach these days is calling around for cheap youth hostels who would be willing to register me for a fee, ie. cost of one night stay, without staying there in reality. I pay them only AFTER they register me first. Shop around because some hostels would ask this fee to be 3 night stay whereas others would be happy with just one. Thus, my advice is if you are staying at a hotel/hostel anyway but for less than 3 days, make ABSOLUTELY sure it is agreed upon (GET THE PERSON'S NAME) when you make the reservation that they would register you with a very short stay. If you don't have to stay at a hotel/hostel at all, and this is all about visa registration, find a cheap youth hostel to deal with it.
By the way, whenever I exited Russia, after handing the immigration officer my passport, migration card and visa registration, they always tossed the registration back at me right away without even reading it while they continued to process the other 2 documents. Thus, I am not sure if visa registration is a formality that the Russian officials still care nowadays. However, since I can 'buy' it from a youth hostel for a few hundred rubles, ie. price of a meal at McDonald's, I don't see a good reason to push my luck by skipping this presumed formality.
