With this hypothetical infinite speed computer you will get solutions that are perfect matches for your test cases but essentially random for all other inputs.
Exactly. Saying that with infinite CPU power you could brute-force a solution is like saying the Library of Babel[1] contains every book ever written. True, in a sense, but not as useful as you might think.
I really don't see what's so controversial about this. The universe can, as far as our understanding of physics dictates, be simulated in finite computational time. This experiment dictates infinite computational time.
Evolution is a purely physical process. Make up a series of tests more or equally complex to those evolution present, and you'll end up with intelligence - unless there happens to be something very, very special about human intelligence as opposed to other forms of intelligence. Humans are currently a local maximum in the space of intelligences which have been explored by evolution.
That's not a brute force approach, and would be a difficult engineering task all on its own, regardless of the infinite computational resources available.
