Its main restaurant was packed with sailors blitzed out of their minds on vodka, slumped face down on grimy tablecloths. Vigilant private security guards patrolled back and forth, walkie-talkies crackling, their long truncheons at the ready, ready to club any miscreant insensible. And that was just inside the restaurant. No waiter appeared when I tried to dine there, but it did not seem a place to complain about the lack of service.
That was back in the early Nineties, when Ukraine was newly independent, but anarchy and the tinkle of broken glass were in the air as the old one-party system collapsed, yet to be replaced by democracy or indeed any kind of government. Nobody knew who was really in charge, because nobody was. Into this power vacuum stepped rapacious businessmen like Sergei, to pick over the remains of the state. Communist officials had become capitalists overnight, still helping themselves to the country's resources. Only now they operated in the name of the free market instead of a centrally planned one.
So I tried the hotel bar where I was presented with a sandwich by the waitress, and several other offerings from my new friend Sergei. A boat, he ventured, perhaps I would like to buy a nice yacht, with plush furnishings and a fancy motor? It was out in the harbour, bobbing gently in the waves. Perhaps, I replied, a boat might be fun to own. Just $30,000, he said, who could quibble at such a cheap price? I hummed and hawed a bit. No boat, he said, OK. But how about a fighter plane? A fully operational MiG 29?
Now he was talking. My own air force. Bank managers, difficult editors would quiver with terror as I buzzed their offices. Why not? This was a time when independent states were sprouting across the former Soviet bloc like mushrooms after the rain, each with its own armed forces. Maybe I could have my own country as well. LeBoristan. It had a certain ring to it.
My first task as head of state would be to start a border dispute with the neighbours. But before hostilities could commence, like every new potentate, I would have to equip my generals with the necessary top-of- the-range military gear. Apparently that would be quite straightforward, now that I had met Sergei. Everything was for sale, especially weapons.
"How much for this MiG then?" I asked, in an insouciant drawl, as though this was the sort of purchase I considered daily.
"Eight million dollars," replied Sergei, taking a long swig from his beer. I considered this and asked how I could get the plane out of the country. "Don't worry my friend, all the paperwork and forms, customs, everything will be taken care of," he said, leaning forward conspiratorially. "You just specify where you want delivery." Eight million dollars, I replied, was rather more than I had budgeted for this trip. "OK, I cannot change the price, but I give you whichever kind of rocket attachments you like, for free, a special gift. Air-to-air, or air-to-ground. You decide."
Welcome to the new Eastern Europe. A region where Communism has been replaced by chaos-tinged consumerism, Marx by mammon, and once stable, unified states such as Yugoslavia - even sedate Czechoslovakia - divide themselves up like so many geopolitical amoebas. Often to the soundtrack of shrill declarations of ethnic and cultural superiority, as long-dormant national disputes, deep-frozen for 50 years, explode once again and new states are born by both blood and the ballot box.
It has been a decade of experiences - some adrenaline adventures, others disturbing incidents that linger still - that I could have never imagined when I first came here in the winter of 1990. For capitalism's Wild East is also the land of opportunity for a journalist. I have hitched a lift home from Kiev to Budapest in a prime minister's private jet, watching from the window as the Ukrainian army band played by the runway, red stars on their caps floodlit in the snow in a Soviet-era tableau. I have looped the loop in a Slovak fighter plane as sky and ground merged into a patchwork blur; stood on set as a hardcore pornographic film was being shot in a Budapest villa; been tear-gassed in both Bucharest and Belgrade (Romanian tear-gas is like a bad hay-fever attack, Serb has you crawling on the floor hunting for air); arrested as a suspected spy in former Yugoslavia; and even captured in a battle in Bosnia.
Other pictures too linger in my mind: a barber cutting his customer's hair under a giant portrait of Stalin in the Georgian port of Batumi; the look of shame on a Muslim woman's face in the Bosnian city of Zenica as I tried, vulture like, to prise out of her the details of her rape by Serbian soldiers; an old lady sitting helpless and crying in Sarajevo's streets as snipers' bullets cracked around her; and the way black flies swarmed over my arms as I walked over the mass graves at Belzec, the Nazi extermination camp in Poland.
But these - and even my Odessa encounter with Sergei - all lay ahead of me when I first settled into my new flat by the Danube in Budapest, where I had set myself up as a foreign correspondent, on a slender retainer and a promise of articles to be printed in The Independent. The Soviets were leaving, and the city was celebrating the end of over four decades of occupation. The Warsaw Pact had collapsed, and so had the Communist trading bloc, Comecon - signed out of existence in the Hungarian capital. The Hungarians, Czechs and Poles celebrated, while the Vietnamese and Cubans looked on stonily. History marches on, unstoppable as ever, especially in this part of the world, where for centuries armies of competing empires - Ottoman, Hapsburg, Nazi and Soviet - have vied for power, leaving their buildings and cultural legacies behind.
For now, at least, soldiers march across hostile frontiers no more, and power stems not from the barrel of a gun, but from the cursors on bureaucrats' computer screens in Berlin and Brussels. The key Central European nations of Hungary, the Czech Republic and Poland are now poised to join the European Union, while Slovenia and the tiny former Soviet republic of Estonia are not far behind. Even Romania, with its endemic corruption, supremely venal officials and ramshackle infrastructure, will be considered for EU membership some time in the next decade. If Greece can join, then why not the lynchpin of the Balkans?
As well as new states, the last decade has given birth to whole new regions of Europe, at least in diplomatic speak - shorthand terms that indicate new aspirations towards the West, or the revival of older ones. Czechs will tell visitors proudly that Prague is a long way west of Vienna, and theirs is the heritage of middle Europe, not the Balkans.
In Hungary, the foreign ministry has conceived of, if not invented, a new part of the Continent, known as East-Central Europe. Quite what makes up this area nobody is quite sure, except that Budapest, three hours' drive east of Vienna, is its epicentre. The message seems to be that Hungary is not Romania, is not in the Balkans and wants very little to do with it. Even though it is right next door, and Budapest rhymes with Bucharest.
Where the Balkans begin nobody is sure either, although the Romanian city of Cluj, in Transylvania, seems a suitable starting point. Cluj was, until the 1920 Treaty of Trianon that reshaped Eastern Europe, known as the Hungarian city of Kolozsvar. Even now the city retains its faded fin- de-siecle grandeur, although its dusty streets are filled with sputtering Romanian-built Dacia cars instead of horse-drawn carriages. Steadily reviving after the moribund decades of Marxism, its greatest drawback is the ultra- nationalist and anti-Hungarian mayor, Gheorghe Funar, who spends millions of lei erecting monuments to Romanian national heroes that would be better used improving the city's infrastructure. For a Briton, growing up in a culture of free speech, democracy, reasonable political transparency and fair play, the Balkan mind-set can take some getting used to.
Once, reporting here, Funar's deputy carefully explained to me how the Hungarian government ran a special college in Budapest from where beautiful Magyar maidens were trained in sexual skills and sent out to enrol in the West's leading universities. They would seduce the best students, likely to become political or economic leaders, and marry them. Safely ensconced in the Hungarian honey trap, he claimed, this network of international politicians would then oppose Romanian national interests whenever possible and work for Budapest's interest. It was nonsense, of course, but still an illuminating insight. Sad to report, after eight years of being based in Budapest, not a single Magyar temptress has attempted to recruit me for the cause of Greater Hungary.
Further down south, in the capital, Bucharest, many Romanians still pine for the strong hand of the "Genius of the Carpathians", as former ruler Nicolae Ceausescu liked to style himself. One recent opinion poll showed 61 per cent believing they were better off under his rule. Nicolae and his hated wife Elena died in a hail of bullets on Christmas Day 1989 - the Revolution's present to the Romanian people, or the convenient removal from the political scene of the couple who knew most about their neo-Communist successors. Either way, nostalgists with enough lei, or preferably dollars, can at least kit themselves out in the Ceausescus' clothes and possessions, recently auctioned off on the Internet. This kitsch collection included a pair of white leather brogues perfect for a New York pimp and rows of womens' suits in fetching shades of pink, yellow and turquoise. Also on offer was a 1975 Buick donated by former US President Richard Nixon, an embarrassing reminder of the way the Ceausescus were once feted by world leaders as anti-Soviet mavericks. They even visited Buckingham Palace, after which several items reportedly went missing.
Now Bucharest, like its neighbours Budapest and Sofia, is slowly recovering some of its pre-war grandeur, but it will be decades, if ever, before the city is dubbed the "Paris of the East" again. The Athenee Palace hotel, immortalised in Olivia Manning's best-seller The Balkan Trilogy and home to generations of spies and secret policemen across the decades, still stands, reborn as a Hilton. The service has undoubtedly improved but the atmosphere of intrigue has vanished.
Ceausescu's lasting legacy to his people - apart from a wrecked economy and crumbling national infrastructure - is his massive, 3,200-room palace, high up on a hill overlooking Bucharest, that still casts a shadow, both real and metaphorical, over the city. Twenty-four thousand workers toiled for five years to build this monstrous but oddly impressive edifice, now used by parliamentarians, and also available for hire for Nato conferences and fashion shows. The balcony looks on to a grand avenue that Ceausescu named "Boulevard of the Victory of Socialism", precisely one metre wider than the Champs Elysees. Nicolae Ceausescu never stood there to receive his people's acclaim. That honour was left to former president Ion Iliescu and, ironically, one of capitalism's icons - the pop star Michael Jackson.
Sometimes it is the tiny, illuminating moments that illustrate how, in much of post-Communist Eastern Europe - even in the countries that proclaim their middle-European heritage - the gulf in mind-sets between East and West will take years to fade. As the episode of the patriotic radish illustrates. It was the winter of 1991, a few months into the Croatian war of independence, and we were dining at our hotel in the capital, Zagreb. The Croatian flag, with its alternate pattern of red and white squares, flew on every street corner, as though the very emblem itself could ward off Yugoslav attacks. The radio was filled with patriotic songs, and the streets with armed soldiers. Across from our hotel was the headquarters of the nationalist HOS militia. Visitors had to leave their guns at the entrance, and the reception looked like an armoury, with Kalashnikovs, machine-pistols and sub-machine guns piled up in disarray.
It was a dark and frightening time, when the Yugoslav army was bombarding much of the country, and citizens in towns and cities such as Vukovar and Osijek cowered nightly underground as the shells and mortars rained down. Even Zagreb was not immune: shop windows were covered in tape to prevent flying glass if bombed. Air-raid sirens wailed out almost daily as the Yugoslav jets flew over, and frightened women and children took shelter in metro stations and underground bars and shops.
Still, even in a war you have to eat. Our stern-faced waiter had recommended "Croatian fish", for dinner, to be washed down with "Croatian wine". Quite how the cook knew the nationality of the fish we never found out, but of the radish's loyalties there was no doubt: the chef had carved out a tiny arrangement of white squares in the red skin of the radish, mimicking the pattern of the national flag.
Later, under fire in the front-line Croatian town of Slavonski Brod, I began to understand why someone would carve their national flag into a vegetable as a symbol of defiance. Pounded for months by Serbian artillery, Slavonski Brod was a ghost city. We drove in on a Saturday afternoon, and the streets were utterly deserted, their buildings pockmarked by shrapnel and shellfire. The very air itself seemed to change as we came off the motorway, somehow tense and pregnant with anticipation of the next explosion that would rent it apart. As the boom of incoming artillery fire became louder, we switched into war mode. The sense of adventure ended, the danger began. Buzzed up on adrenaline, my senses went into overdrive: colours became pin-sharp, intense, and I could hear for miles, or so it felt. We liked to play Seal on the way into towns under fire: "You'll never survive, unless you get a little crazy," he sang, as the backbeat thumped out. It seemed apt enough.
The Yugoslav wars spawned their own version of the Highway Code: stereo off so as to hear any incoming fire; seatbelts off in case we had to roll out of the vehicle quickly; windows open to prevent flying glass; and sunglasses on to protect your eyes. And, of course, try to shrink into your flak jacket as small as possible. Don't think about your legs, or your neck, unprotected. Or the German reporter who bled to death after he was shot in the thigh. Just drive as fast as possible and get underground.
We headed straight for the hospital, asking directions from some policemen behind a row of sandbags. It was the logical place to go, as in most hospitals staff and patients had been evacuated underground into the basement, and the doctors usually had time to explain their work. But in the twisted minds of the Yugoslav gunners, hospitals were a favourite target.
The Croatian doctors were polite, as usual, and seemed pleased that someone had come to see them. They worked in shifts, one explained - a few days on, a few days off, shuttled in and out of Zagreb. One proudly held up a tiny baby in an incubator, a sign of life in this city where too many had died. A doctor took us to his room in the hospital basement where we sat talking until suddenly, by unspoken agreement, we all fell silent as we listened to a whistle overhead. It was clear and sharp, subtly altering its tone until it ended in a not-very-distant explosion. Life itself seemed to be suspended, hanging on the thread of a Serb gunner's trajectory, while we waited to hear where the shell would land.
If you can hear it, it probably won't hit you, colleagues had told me, and if you hear it go off, then it's definitely missed and you are still alive. It missed the hospital and landed in a nearby apartment block. Ambulances skidded out and a few minutes later the first casualties were brought in on trolleys. One man, wounded by shrapnel, greeted us as we watched him being wheeled into the operating theatre, now relocated in the hospital's gymnasium. The floor was awash with blood, under the bright lights.
The bright lights were shining too around the ornate, Art-Nouveau swimming pool at Budapest's historic Gellert Hotel. It was 10 o'clock on a summer's evening, and I was on the set of a hardcore porn film called The Magnificent Seven. Sex films are one of Hungary's most successful new exports, although not the sort of product that the government promotes.
Such is the porn industry's love of Budapest that the city has been dubbed "Bangkok on the Danube". Films shot here are sold all over Europe and the United States. Many of the most sought-after porn starlets are Hungarian, including the most famous, Cicciolina, born Ilona Staller. Pornography is legal, as long as the actors are over 18. Locations such as the Gellert Hotel, an international landmark venue, are cheap at pounds 75 an hour. Producers also find a ready supply of fit and attractive young men and women in Budapest, a city where virtually every corner is the site of a gymnasium or solarium. For a few, having sex on screen for between pounds 100 and pounds 300 a day is an attractive proposition.
But not all the workers in the city's thriving sex industry are so well paid. Beneath the make-up and bright lights on set at the Gellert there is a dark side to the sex industry. Rumours abound of young Hungarian women being lured abroad where they are abused and exploited, forced to perform in hardcore films. The run-down streets in Budapest's Eighth District are filled every night with prostitutes offering sex for less than pounds 10. Many are Gypsies, driven to sell themselves by institutionalised racism and poverty. Others are country girls brought in from Romania and Ukraine, promised employment as a dancer or hostess. Often their passports have been taken away and they are locked into a life of vice by one of the many mafias from across the former Soviet bloc who run much of the sex industry.
But porn producers in Budapest are keen to emphasise that they are filming quality sex. The Magnificent Seven is in a different league to the usual under-the-counter, black-and-white videos, filmed on shaky hand-held camcorders. A budget of pounds 225,000 - high for the sex film industry - pays for professional cameramen, make-up artists and directors. The film was even being shot in three versions: soft-core for cable television; harder core for the cinema, and hardest of all for release on video.
Anita Renaldi, assistant producer on The Magnificent Seven, is a former hairdresser from Dunaujvaros, a small town outside Budapest. She is now one of Europe's best known sex actresses. The question, of course, that I, and almost everyone who meets a porn star, want to ask is this: "How does it feel to have sex on screen with a perfect stranger, surrounded by cameras and microphones that record your every move and noise?" The answer, she claimed, is that she divorces her feelings from her body, although with something as intimate as lovemaking it's hard to see exactly where the division lies. "Everything is false with the man with whom I make a hard scene," she said. "You believe that I want him, but I have to be a very good actress." As for witnessing an actual sex scene, I was reassured to discover that I found the sight of live copulation far more unsettling than stimulating. Even the most unerotic sex is, after all, a supremely intimate act between two people. But here on set lovemaking is reduced to something as perfunctory as urinating or eating breakfast. Lights and microphones hover overhead while a director yells instructions to the actors to speed up or slow down.
And life itself is speeding up. Budapest has transformed itself over the last decade from a drab Communist capital into a buzzing metropolis that will soon be able to compete with Vienna or Munich, the hub of a region being rapidly reborn. The shiny glass-and-steel offices downtown soar skywards, metaphors for the city's reach into a sunny European future. Budapest's architectural heritage has not been neglected: magnificent Hapsburg-era and Art-Nouveau buildings have been carefully renovated, shoppers stroll down pedestrian precincts illuminated by antique street lamps.
A generation has grown up across the region, for whom the Communist states are merely dim - and often happy - memories of socialist summer camps, sing-songs and Young Pioneer uniforms. Many of those in their 20s and 30s work in jobs that simply did not exist until after 1989: as stockbrokers, advertising executives, computer games designers. In fact, watching television in Budapest, it's often hard to imagine that this was ever part of the Soviet bloc. Channel hopping recently, I switched on to a cable music station, modelled on MTV. The female presenter was dressed in Lycra rave gear, the music was the same techno that pounds out of clubs in Berlin and London. After a few minutes the music videos stopped, replaced by share price news. The programme cut to the trading floor of the Budapest Stock Exchange. Young brokers in white shirts ran to and fro, making deals. Thus prosper capitalism's latest recruits. The older generation, unable or unwilling to make the necessary mind-set change, have a harder time, many struggling by on monthly pensions of less than pounds 100 a month.
Perhaps somehow there is a way to combine the best of both worlds, of weaving in the rich cultural heritage of Eastern Europe's past with its promising future. That great middle-European institution, the cafe, could show the way. At the turn of the century Budapest boasted over 300 cafes. They were public lounges, salons for those who rented tiny bedsits with nowhere to sit down. Many were the haunts of writers, artists and politicians. Communism put an end to all of that. Building socialism meant there was no time for long, tobacco- and coffee-fuelled discussions, whose participants might start to question why they had to live as they did. The Party preferred its members to take their coffee quickly and standing up. By 1989 Budapest barely had a dozen proper cafes. A couple of years later, the site of the Central Coffee House, one of the centres of intellectual life in the Austro-Hungarian empire, was home to a bagel bakery and an amusement arcade. But the site is once again being refurbished, for the grand re- opening of the Central.
I hope to visit, especially if the Central lives up to its century-old reputation: "The lamps and the whole interior decoration, like the marble tables, sofas, billiard tables, the games room and the coffee kitchen, moreover even the cups and saucers are so beautiful that it is impossible to imagine anything more so," wrote one regular at the time. Perhaps I might even bump into Sergei there. I shall order a mocha, but no missiles. n
Adam LeBor's book `A Heart Turned East: Among the Muslims of Europe and America' is published by Little, Brown, pounds 7.99