The Cuckoo PoW is divided in two steps. The first step is trying to find a cycle (of length 42) in a graph, and the second step is checking if that cycle meets the target. So when you see in the log Failed to meet target it means you found a cycle, but that it did not meet the target.
There is a 1 in 50 chance to find a cycle, and at the current target there is a 1 in 4000 chance that the cycle meets the target. So, yes you are expected to see lots of those!