To put an end to the uncertainty above:
1) Border Zones correspond to "Raions" (town or county administrative divisions - the smallest administrative divisions in Russia) bordering federal borders and sometimes coastal regions. If the Raion is large then it means the border zone can sometimes extend a fair way from the actual border (50-60 km in sparsely populated areas). Other times, the border zone can be just 2-3 km wide. OSM (when you zoom in far enough) does show the smallest administrative borders in Russia, that of the Raions - allowing you to see the limits of the border zones. It is that traced out by the edge of the raions on the federal border.
2) Border Zones are all listed online ...
Click Here
3) The fact that someone was stopped in the middle of Russia by a man in a uniform does not mean the rider hit a border zone. There are many closed zones within Russia, as indeed there are in all countries (
This clip from Area 51 last year springs to mind), usually military / national security related. These are not "border zones".
4) Travel on a Federal Road that goes through a border zone is permitted without border zone permits. For example, travel down the M52 Chuisky Trakt to Mongolia from the Russian Altai enters a border zone as soon as you leave the town of Kosh Agach, around 30 km or so from the actual border. However, you need no border permit to be on that road, as it is a Federal Road. I do advise people not to camp away from the road in a border zone tho... so while you may use the Federal Road thru a border zone, leaving the Federal Road to camp in the border zone may well contravene border zone regulations.
5) There are hundreds of blogs and ride reports of people riding or driving the M56 to Magadan. You will not find a single reference to getting, needing, showing a border permit for that journey anywhere in any of those blogs. It is either an incredible omission, or its not needed. It would be even a more remarkable omission when almost all of those blogs mentions somewhere, Russian visas. So its kinda common sense guys - if not a single person mentions them in connection with Yakutia or Magadan ... what does that tell you?. As an author of several of those blogs, I can assure you there is no border permit required to do the M56.