Am I right in saying that it was the sheer volume and content/structure of these pages which made things obvious to the Great Google?
In the context of the marketplace, it could be argued that Interflora was the primary flower related brand in the UK. So ranking the main site for local terms makes sense - those were relevant results regardless of the techniques used to achieve them.
What's likely is that this stuff has been on Google's radar for years - I would imagine there would have been loads of spam reports from local competitors.
Purely speculation, but I would guess that Google has ignored the spam until recently because the result returned was still relevant. It's more the tactics used that have drawn scrutiny and probably just got to the point that they warranted action (more businesses using them and the newspaper networks were doing spammy stuff themselves).
It's an unusual case as Interflora don't really have a major national competitor and are a strong offline brand.
What I find interesting in this case is that it's just an example of particularly bad SEO implementation. The business is a franchise, so the parent company will pass on leads to local franchisees. That's a huge network of local businesses - but none were leveraged online (presumably so the parent company can control the sales leads), which left the "SEO need" to create content at the local level (every location they serve). This in turn creates the need for more aggressive link building (dull content isn't linkworthy, and more of it requires more PR to rank). That was just the wrong approach IMO.
The whole site should have been setup differently, which would have largely removed the need for hardcore link building in lieu of traditional marketing, but that would have probably required much more significant management buy-in (and if what you are doing, works, why change it?).
Something we'll probably never know, but it would be interesting to find out how Interflora could have performed organically without such aggressive tactics, given they were such a strong brand. I reckon their brand equity alone could have easily secured local rankings without the need for link building - couple that with strong PR, social media and good content creation and they could have hit their top level generic rankings quite easily too. With none of the risk that copious amounts of exact match anchor text links brings...