Red Square was closed to the public. The stark granite mausoleum holding Lenin's remains was covered by scaffolding and surrounded by rows of blue chairs. A gang of workmen were putting the final touches on a stage that ran the length of the old GUM department store. At the far end of the square, a team from a local advertising agency hoisted up banners promoting the latest Nokia mobile phone on poles in front of St Basil's cathedral.
I asked a bored military officer manning one of the barricades when the square would be open again and he shrugged. "Maybe after the Victory Day Parade," he said. "Maybe not."
The soldier's surly response made me smile. With news that both Ritz Carlton, where basic rooms start at $1,000 a night, and Mamaison were about to bring their particular brand of five-star sophistication to the city, I had come to Moscow to see how much of the Soviet spirit remained. In a city now obsessed with sushi, designer handbags and partying with Ukrainian models, the soldier's brusque reply was redolent with the images I had in my head of babushkas in head scarves, grey apartment blocks and old men clutching vodka bottles.
The mood was lost when a camp choreographer breezed on to the stage and led a group of children through a practice run of a very bad rap routine. The Victory Day parade used to be an annual display of Soviet muscle, the chance to show off the latest bit of nuclear weaponry to the nervous west. Now, it seemed, it was a surreal version of Russia's Got Talent.
At least getting a Russian visa had been a Kafka-esque ordeal. A quick call to the embassy in London revealed that I needed a letter of invitation, hotel vouchers and a ticket stub from a Chelsea home game. I made a half-hearted attempt to organise it myself before getting a company called Russia Direct to do it all for me. They are based in Edinburgh, bizarrely, and for £90 I got a visa, a mysterious letter in Cyrillic and a list of contact numbers in Moscow should I need to speak to anyone. I was joking about the Chelsea ticket, but if it ever becomes a requirement I'm sure these guys would happily sit through a goalless draw at Stamford Bridge to get it for you.
With the visa sorted, my next task was to find an old Soviet-style hotel on the web. I wanted something boxy and dour, set over at least 12 floors with a babushka looking after each one. In a perfect world, my babushka would chain-smoke, neglect her cleaning duties and sell the toilet paper to Georgian gangsters. Unfortunately, most of these establishments have now been turned into business hotels and charge upwards of £200 a night.
Not so the Hotel Asia. It was set in a 15-storey tower block opposite the metro station on Ryazansky Prospekt and boasted a hunting-style pub and a Ukrainian folk restaurant within easy walking distance. Its website offered the choice between renovated and unrenovated rooms. I chose the unrenovated option and got a time capsule of Soviet hospitality circa 1973. There was a rug on the floor, a divan as my bed, peeling wallpaper and a metal tray with two cut-glass tumblers. My floor had its own babushka too, but she let the side down badly by greeting me each morning with a cheery "Zdrasvooytyeh!" (hello) and changing the sheets on my bed daily.
Getting around Moscow the Soviet way was easy. I just took the Metro. It has 165 stations and carries nine million passengers a day. Moscow is supposed to be the most expensive city in the world, but a single ride to anywhere on the network only costs 17 roubles. A card of 20 rides will set you back 250 roubles.
When Stalin ordered the construction of the Metro, he envisaged it as a showcase of his particular brand of socialism. HG Wells told him to save the cash and buy 1,000 London buses instead. Stalin ignored him and peasants and workers were shipped in from all over the country to build it. The Communist Youth League pitched in as well. And the Soviet Union's finest artists were recruited to decorate the stations. It is not an exaggeration to say that each platform is a work of art.
The Metro caters to every taste. Want a bit of pompous classicism mixed in with Empire style and Moscow baroque? Then head for Komsomolskaya on the circle line. Bronze statues of revolutionary heroes? Try Ploshchad Revolyutsii. Art deco stained glass? Novoslobodskaya. Vulgar gilt? Kievskaja. A mosaic of workers admiring the red tractor they have just built? The central hall at Novokuznetskaya.
You can't escape New Russia entirely. The speakers installed along the escalators to play hymns to Soviet productivity now pump out ads for mobile phones. And I'm sure the 24-sheet billboard of a girl in her underwear on the wall in Proletarskaya wasn't what the Communist Youth League had in mind when they decorated the platform with hammers and sickles.
But Stalin would be pleased to see that even today the turnstiles are manned by babushkas as uncompromising as he was. One old drunk guy tried to sneak through without paying and was immediately confronted by a small stocky woman who blocked his way yelling "Nyet! Nyet!" I was terrified even though I had a valid ticket.
My quest for a typically Soviet dining experience was slightly more difficult. When I asked my hotel babushka where she had dined during Soviet times, she said she ate dumplings at home. Now she and her husband eat at My-My. Pronounced Moo-Moo, it's a chain of self-service restaurants where you can stuff yourself for a couple of quid. My babushka liked the black-and-white bovine theme, especially the one in Arbat with a fibreglass cow out front.
A friend gave me the number of Nathan Toohey, the restaurant reviewer for the Moscow Times. He took me to Glavpivtorg, a faithful recreation of the beer restaurants popular with Apparatchiks during the Soviet era. It is authentic right down to the pretty girls in homey green skirts and lace blouses who meet you at the door. Upstairs the thick leather chairs are reminiscent of a gentleman's club. There's a wall-sized map of Russia and a huge desk topped by three Bakelite phones should you wish to conduct a thermo-nuclear war. Dried Caspian roach fish is served on a wooden rack with a stick used to remove the scales. You can drink beer, eat prawns, whack a fish with a stick and pretend it's the Cuban missile crisis all over again. Maybe that's why it's so popular with high-ranking officers of the FSB, the new security service, whose headquarters is conveniently located in Lubyanka Square, just down the road.
Another popular spot with the boys from the FSB is the Sword and the Shield. It is known locally as the KGB Club. CCCP badges adorn the poles outside and the emblem of the former secret service department is proudly displayed in the window. I thought it was supposed to be ironic like Maxim's, the Soviet-themed pizza parlour in Budapest which serves Stalin and Lenin pizzas. But when I tried to take a photo of the life-size portrait of President Putin in a karate outfit hanging over the stairs I was brusquely informed that this was not a good idea. The decor isn't satirical. It's homage.
There is certainly no shortage of Soviet paraphernalia on the streets of Moscow. The souvenir stalls in front of Red Square and on Arbat overflow with reproduction badges, hats and posters from the Soviet era. But you'll find the real thing in unexpected places, too. I spotted a relief of Lenin on Tverskaya ul, a popular shopping street. The cinema on Novy Arbat is decorated with wonderful mosaic celebrating worker solidarity. Unfortunately, the mosaic's socialist message was overwhelmed by a garish poster advertising Shrek the Third directly underneath it.
A few statues and sculptures from the Soviet era have found a home in Park Iskusstv, an unassuming garden that sits beside the Moscow river. Here you'll find eulogies to Soviet women carved in stone, metallic celebrations of the space race, a bronze Soviet adviser pointing the way forward to his noticeably shorter African and Asian comrades. There are a couple of Lenin, the Felix Dzerzhinsky that was torn down after the failed 1991 coup, and a three-metre-high Stalin. The statue of Stalin is backed by rows of faceless stone heads behind barbed wire. It's a reminder of the millions who lost their lives in Gulags and a sobering reminder that my Soviet nostalgia is an indulgence afforded to someone who has not lived through those times.
I tried to get into Red Square for the Victory Day parade but my way was barred by barrel-chested Omon guards dressed in battle fatigues. They are the special forces trained to fight in Chechnya, so I did what they said. Instead, I retired to a bar and watched the parade on television like every other Muscovite. Soldiers marched. Putin rattled his sabre at the Estonians for moving a Soviet war memorial. And the rappers rapped. They were only a small part of a programme that was heavy on girls twirling around in traditional costumes.
Once the parade was over I rode the Metro to Park Pobedy, the station that serves Victory Park, a huge memorial complex that celebrates the Great Patriotic War. Here war veterans with chests full of medals accepted flowers and well-wishes from thousands of Muscovites. Then I followed the crowds to Sparrow Hills, where every person in Moscow had gathered to watch fireworks explode over the city below. At my back was the daunting Moscow State University, one of the seven brutal skyscrapers Stalin ordered to compete with the Americans.
In the end, I never got to see the waxy body of Lenin. Workmen were still pulling down the scaffolding when I dropped by his mausoleum on my last day in Moscow. The only queue I saw was one outside the ubiquitous portaloos at Izmailovo markets. And although there was a man in uniform on every street corner I was only asked for my papers once, on my last day, as I left my hotel.
In one final salute to the proletariat I caught a commuter train from Paveletskaya out to Domodedovo airport. At 63 roubles it's the cheapest option. It was old rolling stock painted blue with a stark grey interior and, because it was the end of the day, it was filled with commuters going home. Old babushkas sat with plastic bags bursting at the seams. A guy dressed in black listened to a Russian MP3 player. Once we got past the golden ring to the apartment blocks and grey factories, the train filled with men wearing overalls and a side-parting in their hair. Then, as the train rumbled past the wooden dachas and through the beech forest on the edge of the airport, a woman wandered through the carriage selling turtle-shaped fridge magnets that lit up when you flapped its flippers.
I had found the Moscow I had come to see.
Way to go
Getting there
BA (ba.com) flies Heathrow-Moscow direct from £125 each way. Russia Direct (russiadirect.net) arranges 30-day Russian visas for £80.
Where to stay
Hostel Asia (hostels.ru/en/hostel-asia) doubles from €60.
Further Information
Country Code: 007.
Flight time London-Moscow: 4hrs.
£1 = 45.46 roubles.
· Peter Moore's The Wrong Way Home is published by Bantam, £7.99.