Interesting question. Let's explore the premise of the question itself a little more deeply first:
"In order to qualify as having multiple brains, the brains must be able to work as individual unit(s) while at the same time being able to cooperate to focus on more intensive tasks."
What does "working as individual units" mean? For example, we have different portions of our brains that are constantly working independently of each other. For example, like you pointed out, different parts of our brain that deal with movement/speech/sight. However, these are very specialized portions of our brain that lack any flexibility to "cooperate on more intensive tasks" outside their domain.
The portion of our brain that has this sort of non-specialized general-purpose nature, is our consciousness. What does it mean for our consciousness to branch off and "work as individual units"? That would imply being able to have multiple streams of thought. For example, one stream of thought that is fully concentrated on read this post, while another stream of thought is fully concentrated on watching Breaking Bad.
Even though many of us think we're capable of this, our brains cannot handle any form of true parallel-processing. Whenever we try to "multitask", our brain is actually time-multiplexing between these different tasks, on a single stream of thought.
There is no evolutionary free lunch, and multiple-streams-of-thought will only come about if it leads to an evolutionary advantage. Ie, we will need an environment that rewards cerebral activity, but not too much of it in any one concentration. Ie, thinking about 2 different things with half-the-processing-power has to be more beneficial than thinking about 1 single thing, with full focus. This can only happen in an environment featuring an abundance of shallow-cerebral-content, such that it benefits from multiple streams of thought.
For most of natural history, this has never been the case. Cerebral activity has rarely been a great evolutionary advantage. And even when it did, the amount of cerebral content available at any one point in time, is limited such that a single stream-of-thought has always been sufficient.
Even in today's world, I would argue that there's little benefit from multiple streams of thought. Even though there's so much content out there, you can still only be in one place at a time, and you only have one pair of eyes to see with. Given that this limits you to a single input stream of information, a single stream of thought is sufficient to process this.
And even though there's so much content out there, there's economies of scale involved in choosing which content to consume. Most human progress has come from deep thinkers who focused on one problem, devoted it their full focus, and achieved breakthroughs that way. Even in today's world, which revolves much more around "multitasking," time-multiplexing between all the different things you'd like to do is sufficient to achieve our goals. Very rarely do we ever benefit from thinking about 2 different things simultaneously, with half the processing-power given to each. Hence why this abundance of shallow-cerebral-content requirement is completely foreign to anything in our world thus far.
Let's look at the next requirement:
"If the creature were to lose one brain, the other brain(s) must be able to assume full control of the creatures body, such that it would be able to function (almost) as efficiently as before. In other words, you can't have a brain that deals with just movement while another one deals with just regulating bodily functions. The brains must be able to "swap jobs" as necessary."
This requirement is going to be tricky. Imagine if you're running a dual-core computer and one of the cores stops working. Would you still expect the 1-remaining-core to perform almost-as-efficiently as your previous dual-core-setup?
If you're using your computer to its full potential, this will definitely not be the case. Losing half your processing power will leave you with a computer that is much more sluggish and slow, even though it's still fully functional.
But if you're not using your computer to its full potential, this could be true. Imagine if the only thing you're using your computer for, is playing solitaire. Going from 2-cores to 1-core wouldn't affect your computer performance in any practical way. The question is: Why would you pay for 2-cores if all you need is 1? From an evolutionary perspective, brains are very energy intensive. Having 2 brains when you only need 1, will put you at a severe caloric disadvantage. To make up for this, you will need an environment that is either:
a) Abundant in energy/nutrition needed to develop/power 2 brains
b) Very hostile and injury prone, such that backup organs significantly improve survival rates
Either/both of these will be needed to justify the added cost involved in paying for redundancy in your brain.
To summarize, if you want 2 brains that are capable of sustaining 2 different streams of thought in parallel, you will need an environment featuring an abundance of shallow-cerebral-content, concentrated within a single physical locations.
And if you want 2 brains that can deal with failures/injuries with minimal side-effects, you will need an environment featuring an abundance of energy/nutrition, and/or very high injury rates.