I have found it a lot easier to get by (talking to locals) in Tokyo using English than in for instance Madrid.

I can't comment on Tokyo but just to offer another point anecdote, I've found it pretty easy to talk to people recently in Portugal, Spain, Germany and Belgium.

Most communication starts with my apologetic expression for the cultural faux pas which is about to commited.

I then move on to a token effort at mangling the local language which finally ends with me being asked to repeat in English by a patient native.

That's just not accurate at all.

It's even less accurate again if you're moving in business/tech circles and not travelling around as a tourist.

No, if you go as a tourist to tourist locations you have better chances. But as a local when you take care of daily things you'll need to speak the local, and that's a given. And really as far as recruiting talent between EU countries goes, the language barrier is real between countries that do not speak officially same language.