According to the Guardian:
London used not to be “a Labour city”. London was defined in its current sprawling form, Greater London, by the Conservatives in 1963: in part to offset Labour support in the inner city by including an outer ring of more Conservative suburbs, the “doughnut” that Boris Johnson decisively gobbled up in his mayoral victories in 2008 and 2012.
For decades, London swung wildly left and right, with frequent periods of Conservative ascendancy. During Margaret Thatcher’s 1987 election landslide, her illiberal, anti-multicultural government did better in London than in the country as a whole, thrashing Labour by 15%. [...]
Well into the 90s, Labour’s electoral weakness in the capital - “the London effect” as it was known by journalists and party insiders – was seen as a major obstacle to the party regaining national office.
So yeah, you're overestimating how devoted to Labour (Greater) London actually is (or at least was [not]).
Similarly, but with more local details:
This is a huge sprawling electoral region whose boundaries were set by the then Tory government under the London Government Act 1963, which established the Greater London Council. In order to overcome the fact that London is indeed “a city that leans firmly towards Labour” the Tories included large swathes of suburbia in this new electoral region. Bexley, Bromley, Havering — places like that.
The people living in these areas don’t regard themselves as Londoners. They talk about going into London, or up to London. They don’t think of themselves as living in London. That’s because they don’t. These suburban boroughs don’t even have London postcodes.
Such areas have always been heavily Tory-voting, and even today the electorate there remains overwhelmingly white, with BAME voters in a small minority. Consequently Greater London has never “leaned firmly towards Labour”, on a consistent basis. The inclusion of these Tory-voting surburban boroughs outside London ensured that.
Over the decades, throughout the history of the Greater London Council and subsequently the London Assembly, the Tories have won as many elections as Labour has in Greater London, on the basis of this reactionary suburban vote.
Unlike its predecessor the London County Council, which was solidly Labour from 1934 until its abolition in 1965, the Greater London Council was always marginal. Labour won the first GLC election in 1964, but in 1967 they lost to the Tories, who retained control in 1970 before losing to Labour in 1973. The Tories won again in 1977 and lost to Labour in the final GLC election of 1981.
Since the establishment of the Greater London Authority, votes for the London Assembly have followed a similar pattern. In the most recent elections, of 2012 and 2016, it was Labour who won by a large majority. But in the first Assembly election in 2000 the Tories got the same number of seats as Labour. In 2004 the Tories gained a majority, and extended it further in 2008.
So the fact that Boris Johnson managed to win two mayoral elections in Greater London tells us nothing at all about his supposed ability to reach voters beyond his party’s “comfort zone”. What it demonstrated was his ability to mobilise the Tories’ existing suburban vote.
Check out the figures for the 2008 mayoral election. Overall Johnson got 139,772 more first preference and valid second preference votes than Ken Livingstone (1,168,738 compared with 1,028,966). But in the GLA constituency of Bexley & Bromley alone, Johnson got 86,789 more votes than Ken (134,678 as against 47,889). In other words 62% of Johnson’s total majority across the whole of Greater London was accounted for by voters in this single predominantly white, traditionally Tory-voting suburban GLA constituency.
Contrast this with the support Johnson received in the North East constituency, comprising the boroughs of Hackney, Islington and Waltham Forest, where he got 65,784 first and valid second preference votes as against 111,864 for Ken. In Lambeth & Southwark too Johnson finished well behind, with 55,601 votes compared with 93,692 for Ken. Yet these are the very areas of London that are “home to large numbers of people with university degrees and people from minority ethnic groups”. [...]
Far from winning over a Labour-leaning city, Johnson became mayor of London mainly on the basis of votes from people who didn’t actually live in London. [...]
It’s not often I quote the Daily Telegraph favourably, but in 2008 this is how that paper assessed Johnson’s election as London mayor:
“Mr Johnson’s victory was in part secured as a result of the increased numbers who took to the polls, as his team’s successful ‘doughnut strategy’ of wooing natural Tories in the outer boroughs who in the past failed to vote in London elections proved devastating for Labour. The toppled mayor, Ken Livingstone, proved equally successful in getting the vote out in his inner London heartland, but was outnumbered by the more numerous suburban residents.”
So, increased Tory support/mobilisation in Tory strongholds in Greater London appears to be the (bipartisan) explanation, coupled apparently with Labour's lesser ability to motivate their own inner-city voters when Johnson ran.
The BBC has a comparative map of the 2012 vs 2016 London mayoral elections. Alas these maps are somewhat coarse-grained.
I only found ward-level maps for the 2016 election. But on the latter, more fine-grained map, you can still see a large part of the Conservative doughnut/belt even for the 2016 election:
