I just spent a couple months in russia. I reg my visa in moscow, cost 45 bucks, & I wasnt asked for it at the mongolian border. I still have the paper. When I returned to RU, I spent 3 weeks, 1 nite in a hotel in chita, never registered, & was never asked anything when I caught the ferry out of vlad to japan. I wouldnt worry about it.
However, if you are leaving russia thru the vladi port, be prepared for endless BS, it took me over 2 days at customs, & I had Yuri helping. You will need him, let me know if you need his info. best 60 bucks I ever spent.
I'll never leave from vladi again if I can help it! Last time I left thru Zarubino port, & had no problems