The Murdochs and Lord Rothermere are fans, and media veteran Jonathan Durden calls him "a professional scavenger" and "a human dynamo".
Boxing promoter Frank Warren regularly texts him dirty jokes, while Global Radio's Stephen Miron and Telegraph Media Group's Murdoch MacLennan phone Media Week from their travels to offer praise.
Mike Anderson, an important player in the newspaper industry, has a contacts book to make any self-respecting journalist sick with envy. Contacts are the lifeblood of the media industry, and contacts will go a long way towards determining whether Anderson makes a success of his new venture - a consultancy called Frank Business, named after Anderson's no-nonsense business manner.
Anderson is a big bear of a man - both by reputation and presence - cultivated by 35 years in media, 10 of which have been spent at the sharp end, as managing director of The Sun, News of the World, Evening Standard and Metro. Yet he cuts a strangely dislocated figure in his new high-rise office near Chancery Lane, away from the inky presses and commercial hubs of the newspaper powerhouses of Associated Newspapers and News International.
He still has presence however, an aura that suggests he has won more boardroom battles than he has lost over his career, whether against editors, agencies or consultants. Consultancy is where he finds himself now and, like any consultant worth their salt, he claims Frank brings something unique to the market. "It is a business consultancy, not a marketing consultancy, which will take businesses through efficiency drives and offer creative advice," he explains.
Frank's USP will be Anderson himself and the kinds of doorways he can push open for his clients. News International, Anderson's employer for the past five years, is not a bad start as the company's first client.
He says: "I am working with NI, specifically on The Sun, with editor Dominic Mohan. I am attending title meetings and the strategy is about linking the commercial and editorial world. But I didn't start the conversation about me leaving News International by suggesting it should be my client. That was a nice surprise."
Yet those who believe Frank will be a media love-in, with Miron and his mates thronging Frank's corridor, would be minded to know that Asda, Société Générale and the Chinese government are also working with the consultancy.
Life has changed profoundly over the past two years for Anderson after the tragic death of his wife Jane to cancer, which left him with three young daughters to bring up and, after a break from work, bereft of a role at News International.
He recalls: "It was a difficult time - it is very different being a single parent. But I go about it with a passion. When I came back, News International couldn't find a role for me. They tried to find something, but I thought the best thing to do would be to get out and do what I believe in."
It would have been easy for Anderson to land himself a well-paid job at the top table in media. But hats off to him for going it alone: the enthusiasm for newspapers and the psychological warfare played out by its proponents still burns inside him.
To witness Anderson fully animated is to see him talking about the big players in newspapers. Richard Desmond is a "good operator", London Evening Standard owner Alexander Lebedev has "balls", while smash together the Murdoch and Rothermere operations and you get "an amazing business".
His big regret is that, during his spell at Associated, he didn't have the conviction to back his belief that a hybrid model of the Evening Standard and Standard Lite would be a success.
He says: "The reason the Standard failed in the paid-for space is because Associated was not 100% behind the hybrid model. I still feel this was the right strategy and if it had been pursued with conviction, there would have been no thelondonpaper and no London Lite."
The point clearly irks Anderson, although another school of thought is that his aggressive approach was counterproductive at the Standard. Some contemporaries suggest News International was committed to getting a bit of the afternoon action, while others claim Anderson had a few enemies at Associated who were out to block his plans.
An ex-colleague recalls: "Mike had a lot of ideas at Associated, and some of them were very good. The problem was that his good ideas, including the hybrid model, were blocked by those who were against him."
The incident has turned Anderson into an evangelist for key business mantras, such as his constant references to "100%" - "If you are not 100% behind an idea then it will fail" - that populate the conversation.
He tells an amusing anecdote about how his convictions once got the better of him during his spell as managing director of Metro. "I went to see a client and explained that Metro was so popular that people were rushing to the stations early in the morning to get their copies, which was why productivity was so high across the country. I left that meeting and thought to myself: ‘I think I may have had too much medication the day before.'"
After spending an hour with Anderson, it is clear you would rather have him on your side than against you. With his unmatched operations experience and bulging contacts book, he is offering something new in the consultancy world.
After a tough year, Anderson is looking to the future with renewed optimism and a fearless, frank approach.
NI's move to paid-for content Nobody is holding up a sign and saying giving away content for free is how you make money on the internet. At the moment, newspapers are simply providing fuel for others to make money.
His reticence to give interviews I have not given many interviews. When you work for a media owner, it is always best to keep your head down. Many media owners are putting their heads up too often.
Boston Consulting Group reviewing NI's operations It achieved its objectives and created significant savings across the organisation, which James Murdoch has reinvested into editorial. The reorganisation of the commercial side has not been easy, but the division is now getting into its stride and there is a lot of talent on that side of the business.
Media agencies I don't think there needs to be contraction in the market. What happens in a recession is that entrepreneurs pop up. I would hate to think we lived in a world where there is no PHD or Naked being launched.
Founder, Frank Business
Managing director, News Group Newspapers
Managing director, Evening Standard
Managing director, Metro
Marketing director, New PHD
New business director, CIA
Client sales manager, Evening Standard
Marketing manager, Yorkshire and Tyne Tees TV
Client sales manager, The Mail on Sunday
1984 to 1994
Various roles at The Scotsman, The Observer and Daily Mirror