For many people that's because of his bold approach at Nokia, from his "burning platform" memo to mocking Samsung at the Lumia 920 announcement for announcing a phone they couldn't even demonstrate.
Satya Nadella pipped him to the post for that coveted position in February. The acquisition of Nokia's devices and services arm by Microsoft and its change of name, to Microsoft Mobiles Oy, will also mark the return of Elop to the fold.
He can be outspoken: back in 2009 he called the idea of putting everything in the cloud instead of using software on a device "hogwash." But his record on predicting trends is generally better than that statement suggests: at the same time he talked about consumer technology and social networks arriving inside companies, and both are commonplace now.
He's certainly pragmatic. Faced with operator complaints about Skype undermining call revenue, he cleverly turned it into a way of working with the networks: "Instead of them just complaining about Skype, we can have a conversation. Some operators are looking at bundling Lumia, Skype and their own services with higher-bandwidth allotments to actually charge the consumer more and generate more revenue."
But he also managed to turn around Nokia's culture, which ranged from paranoid (a Nokia developer once told me the company couldn't open source its LifeBlog software because people hated Nokia and wouldn't participate) to stodgy.
In 2011, Elop described Nokia as "reliable, durable, trustworthy. We comb our hair neatly each morning, we pick you up after school when we say we will, we always send you a birthday card." He managed to get the reserved Finns to speak up in meetings and to make firm commitments, and there's a new excitement among even long-time Nokia employees.
Nokia has lost the massive market share it used to have; that was a trend that started long before he arrived there, and while selling the phone business to Microsoft can't have been what the Nokia board originally hoped for, you have to give Elop and Nokia credit for most of the success for Windows Phone 8 (since over 80% of all Windows Phones sold are from Nokia).
When Nokia head-hunted him in September 2010, he was running Microsoft's Business division; that included Office and unified communications – Exchange, SharePoint, Lync, Project and Dynamics, as well as the Office applications. He was running Office when Office 2010 and the Office Web apps launched, and Office 365 was still in development.
The Office Web apps weren't an immediate hit, but they were an important step in putting Office tools on more platforms than just Windows and Mac. At the time, Elop said the danger for Microsoft wasn't competition from free tools like Google Docs but resting on its laurels and not innovating enough. "We have to be out innovating the competition; at the end of the day if we provide more value we'll win."
Elop's team has gone on to success
Other products were definitely successful. SharePoint 2010 was one of the key milestones for the product and Exchange 2010 was also a significant launch, especially as it was followed by both Google and Apple (and indeed Nokia) licensing the Exchange ActiveSync protocol. At that point, the Exchange team was run by someone who's worked with Elop a lot since then: former Windows Phone head Terry Myerson, who is now in charge of all operating system development at Microsoft.
In fact, a number of people who worked for Elop in the Business division have gone on to senior positions inside Microsoft.
Kirill Tatarinov now runs Dynamics, Microsoft's software for running businesses (that's what Delta is using to power the Lumia handsets that cabin crew now use for all on-board sales). Antoine Leblonde is a Corporate Vice President in the Windows division (looking after the development of Windows) and Amy Hood recently took over from Peter Klein as Microsoft CFO. It's not clear how much of a mentor he could have been in a little under two years, but it certainly emphasizes how important the Microsoft Business division has been as a place for key Microsoft leaders to prove themselves.
Microsoft recruited Elop from network hardware vendor Juniper; he only stayed there for a year as Chief Operating Officer, but it was good enterprise experience. Before that he ran Adobe's sales, support and marketing groups, a job he took after successfully negotiating the merger of his company Macromedia with Adobe (he had spent seven years working his way up to CEO, earning the nickname 'The General' for his no-nonsense approach).
Macromedia brought Adobe both the Flash player that made them ubiquitous (which Elop had pushed Macromedia to develop for early mobile phones) and the expertise in web development tools that will allow Adobe to replace Flash with HTML5. Before that he had a tastier job; CIO at Boston Chicken and Einstein Brothers Bagels (now the US fast food chain Boston Market).
Despite the way he killed off projects like Meego that many at Nokia had pinned the company's hopes on, Elop has few detractors. Perhaps it's his down-to-earth attitude and the way he's seen as a steady pair of hands. Tributes to him are usually along the lines of 'very smart' or 'very hardworking'; when Elop left Microsoft, Ballmer called him "a good steward of the [Office] brand." Or perhaps it's the way he tends to roll up his sleeves and join in; at university he helped lay 22km of Ethernet cable to create one of Canada's first Internet-connected networks.
With Windows Phone a solid number three in the phone market and Surface sales languishing, he's going to have to roll up his sleeves and get down to work again now he's back at Microsoft.
- Why not read: Ballmer leaves Microsoft. But in what shape?