Things have changed dramatically since the trip undertaken by Samba was made by Third World heroes such as the Senegalese film-maker Usmane Sembene or the Palestinian leader, Mahmoud Abbas. An estimated 400,000 Africans passed through the Soviet Union, grabbing above-average educations on the way. During the Brezhenev years, mixed-marriages were not even particularly frowned upon.

Central to the Kremlin's plan to spread Socialist soft-power was the Patrice Lumumba University. Luis has been studying here for two years and his fine features bare the traces of stress. He speaks very softly. "The teachers are making racist comments in the classrooms. I can't bear the streets. It's just too much for me. I spend my whole time in my room when I'm not studying." His contemporary from the Democratic Republic of Congo, Gamo, looks like a mixture of the brave and the laughable decked out in Rapper-chic. "Man, we call ourselves the hardest ‘hood. We have to put up with white racism here like no black man anywhere." The experts estimate that there are at least 200,000 active Russian neo-Nazi gang members. In 2003 they struck out at Patrice Lumumba University. An arsonist set fire to one of the residences and blocked the exits, killing 40 students. The fire services blamed an electrical fault, to the rage of Lumumba students. Soon afterwards, two skinheads were seen running away after a second attack was stopped in its tracks. Shockingly, there was no police investigation. Last March, three Chinese students were attacked by a gang of young men just outside a dormitory. One of the students died of his injuries.

You might expect the children of Russia's wealthy to hold Western attitudes towards skin-colour. Maria and I were having cocktails in a Moscow bar that she thinks is glamorous. The daughter of the Vice-President of a leading Russian oil company, she giggles with her girlfriends about black men. The sexual innuendo leads into a discussion about how much it costs to rent them out for parties. Maria seems shocked when I ask her how this is possible. "This is Moscow. You can rent anything." Her chain-smoking friend, clad in expensive brands, butted in: "My friend rented some blacks for a party. They were dressed all in white and paraded around in these lovely gloves. Some of us had only seen blacks on TV, it was so funny."

I phoned up Elena Nuryaeva, a prestigious events organiser, to see how common this is. Her voice is a mixture of a Grace Kelly impression and a Siberian accent. "People find them very exciting. It's common enough. Recently I was at a private birthday party at the luxurious Rai-Paradise Club. For entertainment there were several black men dressed in caricatural ‘Disney' outfits for people to stare at. They were there for titillation by virtue of being black. Recently I was at a Tequila party, an event opened to a wider public held by the Tequila brand Olmeca. Dozens of Africans had been hired out and painted in gold."

Behind this behaviour lies the politics of the past ten years. Nikolay Petrov was once an adviser to the Russian government. Now he is scholar in residence at the Carnegie Endowment for International Peace in Moscow. Petrov believes that the fall of the Soviet Union left a "lost generation of young men who seek to fill the vacuum with racist hatred and violence." He argues that "these great feelings of humiliation experienced when Russia ceased to be a superpower lent themselves to nationalism, which Vladimir Putin has used in part to legitimize his regime." Experts share this sense that the Russian leader has abetted the rise of such attitudes. Ida Kuklina, an activist and researcher at the Russian Center for Human Rights, also blames Putin for inciting racism among Russian youth. "Putin has a personal obsession with strength," she says. "It's very clear to me that black students or lost immigrants are just the most visible targets of a deeper and far more intense attitude." Kuklina suggests that the attacks on black students are the manifestations of a deeper and more threatening racism.

Back when Obama was gathering steam after the Iowa primary, I found myself in St. Petersburg once more. I was with a very beautiful woman, but it wasn't going very well. Drinking cheap Russian fizzy wine, misleadingly called Champagneskaia, had given me a permanent headache. I was smoking too much and now had a cough. I felt trapped by the winter and the cultural gulf between myself and my Russian girlfriend. I thought talking about Barack Obama might be an easy filler for an awkward afternoon, but she had firm views: "He will never win. He's black. And they are anthropologically different from us. Lazy and stupid." I spoke about Nelson Mandela, and then changed tack. "But what if I was Black?" I asked. "Then I would never be with you." Perhaps I should have known then that, after the break-up, I would receive a letter heavily laden with anti-Semitism.

Baudrillard claimed to have been sitting in Sheremetevo Airport, before even going through customs, when he came to understand that the U.S.S.R. had, far from liberating the mind, acted as a glacier over Russian attitudes to "others." Russians think about blacks, Jews and women in the way Europeans did a generation ago. Totalitarianism meant that they have never thought through racism and prejudice, and Putin's regime has made it less likely that they ever will. Obama might be wise to remember that Russians attitudes are distinctive, old-fashioned and sometimes dangerous, and not just on the societal level. The wars in the Caucasus would suggest they affect geopolitics as well.