Luckily, our universe has exploitable structure. The No Free lunch theorem is as much a headache to Searching as the Halting problem is to programming - not really one.
Problems like classification come from a very tiny corner of the "all possible objective functions", so NFL doesn't really apply.