Yes, after the 1948 Berlin Blockade the Soviets and Western allies also agreed on land routes from West Germany to West Berlin. There had of course been previous traffic, but unlike the air corridors it hadn't been guaranteed by written agreements. The original road and rail link was from Helmstedt/Marienborn (Checkpoint Apha) on the inner-German border (British zone) along the autobahn to Dreilinden-Drewitz (Checkpoint Bravo - Checkpoint Charlie was of course the one for allied road traffic between West and East Berlin). This remained the only route for allied personnel throughout the Cold War. There was another rail link from Wartha-Herleshausen (American zone), but I think it was for civilian goods only.

There was initial oral authorization of ten trains per day by the Soviets, later increased to 16, but during the blockade all land connections were cut. The initial thought of General Lucius D. Clay, then military governor of the US occupation zone in Germany, actually was to march troops up to one US, British and French division each along the autobahn, since nobody then believed West Berlin could be supplied just by air. Clay thought the Soviets were bluffing, but it would have risked war. After the success of the airlift, the Soviets also agreed to the land connections in 1952. There was then a parallel road link to the rail line from Wartha-Herleshausen, and a third from Juchöh/Töpen (Rudolphstein/Hirschberg after repair of a crucial autobahn bridge in 1966).

After the election of Social Democrat Willy Brand as West German chancellor in 1969, inner-German relation thawed by way of his Ostpolitik seeking detente with Eastern Europe, namely the 1970 Moscow Treaty. In 1971, the four allied powers signed an agreement on Berlin in which the Soviets guaranteed all transit between West Berlin and West Germany, and the same year both German states concluded an agreement on extended routes. In 1973 both acceeded to the UN, and the following year the US recognized East Germany. However, the new agreements chiefly concerned German traffic; allied transit remained subject to previous regulations and control by Soviet, not East German authorities, who had no business with it.

The Western allies also never recognized East Berlin as the GDR capital since its status was governed by the last joint agreements after the end of WW II pursuant to the 1944 London Protocol, which also covered the military liaison missions. The Soviets increasingly condoned the GDR claim, and the 1971 Berlin Agreement was kinda lofty about the question; though OTOH they never gave up their rights under the allied agreements. There was also some tension between them and the East German government over the missions, as the latter gave up on the aim of German reunification in the late 50s already and stressed its sovereignty as an independent state.

Obviously the activity of the missions was a thorn in their side, and the Stasi closely shadowed and sometimes assaulted mission tours despite having no authority for it. Which led to a string of incidents including the death of an East German soldier in 1969 and a French mission NCO in 1984, almost exactly a year before Major Nicholson was killed. The Soviets paid lip service to backing them up, but naturally wouldn't help them to get rid of the missions, since the benefited from reciprocal arrangements in West Germany. About which the West German government wasn't happy either - and sometimes West German police tangled with the Soviets despite having no authority for it, too - but overall accepted it, since the underlying allied agreements also made the four powers' consent condition for eventual German reunification.