Why is there a strip of uncontrolled airspace between Russia and Norway?
Details of the No FIR area

The area extends on 175,000 square kilometers:


From ≈70°N (Bodø FIR) to the North Pole.
From 30°E to ≈32°05'E, and to 35°E for a portion east of Svalbard archipelago.


  

VATSIM Murmansk sectors (ATC simulation). Source



Border dispute

This Barents Sea strip is of major importance, and has been subject to a dispute between Norway and Russia for 44 years. The reasons include:


This area has been the maritime border between East and West blocks during Cold War (the country is neutral, but still a founding member of the NATO).
Norway is a country with many resources coming from the sea (fish, oil, gas), the sea area controlled by the State is six times its land area. 
The Barents Sea is a location with multiple oil and gas fields to be exploited. The large Shtokman gas field (label "5" below) discovered in 1988 happens to be in the vicinity, an agreement was signed between Norway and Russian Federation for the development of the field, but only in 2005:


Oil and Gas in the Barents Sea (red dots are gas fields). Source
The area encompasses the most direct potential route between Europe and the Pacific after the ice floe has melt down.


This dispute was closed when a new treaty entered in force on July 2011 with the border crossing the 175,000 square kilometers disputed region in the middle.


(Source: BBC)

While the border is now settled, responsibilities for air traffic control are still to be formally defined by international bodies.

Currently transiting flights have to be authorized by respective authorities before operating in this area, e.g. London-Tokyo flights using Arctica 1 route, noted B483 on first picture. In addition of commercial flights, the Arctic region is highly monitored by manned and unmanned aircraft.

ICAO and Eurocontrol status

ICAO wants to resolve this issue of missing FIR:


  8.1 IATA brought the attention of the Group to a portion of airspace of unassigned responsibility, extending from the North Pole over the
  High Seas between Bodo Oceanic FIR, Sondrestrom FIR and Murmansk
  Oceanic FIR (Appendix E refers). Considering the increase d interest
  of establishing new ATS routes through that airspace, the Group agreed
  on the following Conclusion:
  
  TRASAS Conclusion 2/4 – Airspace of Unassigned Responsibility over the
  Arctic Ocean
  That the ICAO Secretariat be invited to take the
  necessary actions to resolve the pending issues regarding the portions
  of airspace of unassigned responsibility extending over the High Seas
  between Bodo Oceanic FIR, Sondrestrom FIR and Murmansk Oceanic FIR


Source:
Report of the Second Meeting of the Trans-Regional Airspace and Supporting ATM Systems Steering Group (TRASAS/2) (Bangkok, Thailand, 18-19 March 2008)

There is a proposal under Eurocontrol auspices (proposal 95.012) to close the topic by Summer 2021:


  FIR border realignment Murmansk FIR / Bodø FIR / Norway FIR:
  
  Objective: To resolve the long-standing issue of the unallocated
  airspace (NO-FIR area) between Murmansk FIR and Bodø FIR / Norway FIR.


Source: European Route Network Improvement Plan 2019-2024

No aeronautical services

Flying in a no FIR area (when such territory is not forbidden to aircraft) means there is no information service provided from the ground. Flight information service consists on informing aircraft about meteorological events, known other aircraft position and intentions and aids availability. Other services are not available either: No alerting (search and rescue) and no ATC. The related airspace belongs to none of A, B, C, ..., G classes.

For those who want to know more about FIR and Oceanic Control Area, see Who manages International Airspace Traffic?

No FIR areas in general

Regarding the existence of "No FIR" areas:


  3) FIRs have not been established for a few areas in the world.
  These are commonly called uncontrolled information regions or “no
  man’s land.” The largest of these areas is in the South Atlantic
  Ocean, annotated as “No FIR.” Flight Information Services (FIS) also
  do not exist in the high altitude structure in other large areas
  (above the top of controlled airspace). Within no man’s land, aircraft
  separation (prevention of collision) is entirely the responsibility of
  the PIC. Advice and information for the safe and efficient conduct of
  flights is not provided from an ATS unit. An ATS unit does not provide
  alerting services related to search and rescue.


Source: FAA 8900.1 - Flight Standards Information Management System - FSIMS (Vol 4-105-C-3)