The name's Monte - Frank Monte

He's 'the world's most famous private investigator'. He hobnobbed with Onassis, hired an army for the Sheikh of Dubai, and knows the truth about Versace. At least that's what he claims.

Frank Monte wants nothing more than for the world to love him, an odd impulse for a man of his particular chosen profession. Monte is a private eye – the best in the business, he says – and normally that would imply a man who hangs back in the shadows, a lone operator, someone who keeps his cards close to his chest for fear of exposing himself by revealing too much of his game.

But that isn't the way Frank Monte operates at all. He schmoozes with the rich and famous. He dresses flashily and parties at all the most fashionable nightclubs, from New York to the Côte d'Azur. He runs around the world collecting celebrity clients and then bragging about them. He offers tip-offs to what one might politely call the lesser quality newspapers, and in return, earns himself a welter of press coverage, all the better to reinforce his claim to be "the world's most famous private investigator".

Twice in his career, Monte has forced world attention upon himself through the sheer chutzpah of his professional undertakings. The first was in the 1970s, when he became associated with a series of romantically adventurous exploits, including a spell as Aristotle Onassis's security advisor and a seemingly incredible project to raise a private army for the Sheikh of Dubai.

The second was in 1997, when Monte claimed to be privy to the secrets that led to the killing of Gianni Versace.

The Versace affair made a particularly loud splash because Monte announced that the fashion designer was a client of his; apparently, the two of them met in a series of secret assignations in New York's Central Park and elsewhere. Monte's theory of who really was behind the killing – he does not buy the official Andrew Cunanan gay serial-killer hypothesis – proved so explosive when he first talked about it that it unleashed the full wrath of Versace's lawyers. This newspaper, among others, is now legally bound not to repeat his allegations.

To say that people have trouble believing the stories that Frank Monte tells would be an understatement. Even his claim to have brought up his two sons alone, following a spectacularly acrimonious divorce from their mother, has been questioned by the press in his native Australia – not to mention his wild tales of bringing back the skull of Michael Rockefeller from the jungles of Papua New Guinea, or his account of tracking down a group of dodgy Colombian middlemen who supposedly swindled Jack Nicholson and Marlon Brando out of $6m.

Still, Monte tells his tales in the full confidence that people are eager to hear them. For the past 10 years, he has been promising an autobiography. Seen by The Independent in proof form, it is an intriguing document, confirmation of all the braggadocio for which Monte is celebrated. "I've led an interesting life," he writes. "Over the past 35 years, I have been detained by authorities, thrown out of countries, asked to leave others. I have been shot at, bashed, and had my nose broken and teeth smashed more times than I care to remember.

"I've achieved the world record for collecting evidence in divorce cases. I've made two films, and may even finish my third one day. I've guarded rock stars and executives, hired an army and then fought with it, and travelled in my own version of Heart of Darkness, along the remote waterways of Irian Jaya.

"In the course of all this, I became a millionaire with a fabulous art and antiques collection, many properties, a Rolls-Royce and a Ferrari, and a series of glamorous girlfriends and famous acquaintances."

He might as well have added: "The name's Monte, Frank Monte." He certainly has the white dinner-jacket to match, as the lavish array of photographic inserts attests. In the introduction to the book, he says that he is writing "to set the record straight", apparently to convince those doubters who wonder how one man could have crammed so many adventures, wealthy benefactors and beautiful women into one lifetime.

But the book (whose title, The Spying Game, is not as telling as its subtitle, My Extraordinary Life) does not seem to be written with an official record in mind at all. Nothing about its narrative style seems remotely designed to assure the readers of its veracity, a point that Monte conceded when I caught up with him in a phone call to his lawyer's office in Sydney.

"It's not fiction as such," he said, a touch defensively, "but it is in the fiction genre. What I set out to do was to write a fast-moving, fictionalised-type film-noirish autobiography. You know, bring on the sex'n'drugs and rock'n'roll." That does not mean, he added hastily, that the book contains anything other than the truth.

The name, it turns out, is not Frank Monte, or not exactly. He was born François Ferdinand Antoine Montanari, the son of Italian expatriates in wartime Alexandria, and grew up speaking Italian, French, Greek and Arabic, as well as English. Not a bad start for the aspiring spy. The real fireworks began in the early 1970s, after a tedious spell on the Sydney police force and some routine adultery work in private practice. Monte's first big client was an Australian businessman so affronted by a New York banker that he wanted him killed. Although Monte had no intention of committing murder, he took the job – for A$8,000 up front and the promise of another A$6,000 on completion – only to have his task made much easier by the accidental death of the banker's wife in a road accident.

The client was delighted, letting himself believe that Monte was somehow responsible, and spread the word that his investigator was a ruthless killer. "This actually helped build my mystique," Monte writes. "In this game, a ruthless reputation isn't bad for business."

He met Onassis in 1973, and was soon – by his account – procuring young women with whom the oil magnate could adorn his business parties in Rome. The Sheikh of Dubai episode followed – a tale too complex to recount here, but which involved fire fights, near-death experiences, the Dubai secret police, young American women tourists possibly doubling as CIA agents, and a chase through some of the fanciest hotels on the French Riviera.

The reader's credulity is stretched further as Monte recounts his adventures in Papua New Guinea to unearth the mystery of Michael Rockefeller's disappearance in 1961. There are headhunters, skulls aplenty, massacres by Indonesian troops, and the whiff of a homosexual affair between Rockefeller and the son of a tribal chieftain. If even a fraction of it were true, it would sound like a Hollywood film – which is what Monte tried to make it into when he moved to Los Angeles in the late 1980s. LA seems to have defeated him, however. He met plenty of celebrities, but his work seems to have consisted largely of routine bodyguard jobs.

Meanwhile, his film languished in development and was never made. "I don't even like to stop off in LA on holiday," he said in our phone interview. "I've got a problem staying there any more than a couple of days." New York, where he moved in 1995, suited him altogether better until the Versace murder. What could have been his most famous case blew up in his face because he was never able to produce any proof for his allegations.

And now it is the Versaces, once again, who are causing trouble for his book. The Versaces, that is, together with a disgruntled ex-girlfriend called Justine Ski. Between them they have torpedoed his credibility and persuaded his publisher, Pan Macmillan, to withdraw 25,000 copies of The Spying Game as it was about to reach the shops.

Monte has many explanations for this new débâcle in his life, some of which are contained in two $5m defamation lawsuits he has launched in Australia against Ski and The Australian. He is considering, too, whether to sue his publisher. The book has not been pulped, he insists, and may yet come out. Meanwhile, he fulminates against the Versaces, and says he hopes to see Donatella Versace "dragged off in chains" one day. Whatever the accumulated riches of his past, it is clear that Monte, now 56, is down on his luck. He accepted an advance of A$30,000 (£15,000) for the book, a paltry sum for a man who says it was not unusual for a celebrity to offer him hundreds of thousands in cash for his services.

Monte blames the end of the Cold War, the advent of the internet, his growing disgust with his profession, Australian "tall-poppy syndrome" determined to cut him down to size – everything, in fact, except his own skills and choices. He comes across as a rather sad figure, caught up in increasingly trivial battles with enemies big and small as he seeks in vain to find someone who will still believe him. He has been single for two years, his mother recently died and one of his sons has been in trouble of a kind he declines to specify. Being ditched by his publisher and, for good measure, his agent, hasn't improved his mood.

However, now that he has reasserted the rights to his book himself, he has managed to find two publishers. That's the good news. The bad news is that they are in Peru and Iceland. Which leaves a whole lot of world that still has to learn to love Frank Monte.