The main problem with branches in an algorithm like this is that they create a dependency, where not only do the future instructions depend on the possibly-mispredicted outcome of the previous instruction and need to get thrown out, but you may have started executing the wrong instructions.
A cmov doesn't affect the instruction pointer, so that 'executing the wrong instructions' condition is gone, but it still affects the output of all following instructions if they depend on the register it modifies. So you still have to worry about pipelined work being thrown away on a mispredict.
IMO, cmov was far more valuable back when it was new, because branches were more expensive then. IIRC it was added to x86 in something like the MMX or SSE1 era, so a very long time ago for very different processor architectures. It's still a useful instruction category to have, if only because it lets you produce smaller code (and smaller code is usually faster), but I expect the value is less significant than it used to be.
Incidentally I am curious whether Linus's position on cmov back in 2007 is one he still holds today, and whether his assertions hold up on a modern Intel or AMD CPU. https://yarchive.net/comp/linux/cmov.html
I think the branchless search in this blog post is faster simply because the inner loop is much smaller. The observation that it sometimes does extra comparisons explains why it is slower for an expensive comparison operator, because the advantage of the smaller loop is gone. I don't think it being "branchless" is terribly important in comparison. You could try to fudge an experiment to prove this by inserting extra instructions, but they would need to be ones that decode into actual executed uops, and you'd need to decide whether they should have dependencies or not.
In the bad old days when I got promoted to the programming team at a job they had me take a test, and one of the tasks was to write a transparent blit routine. The one I wrote was "branchless", but because cmov intrinsics weren't widely available I achieved this by using an array of pointers and selecting the array index based on the result of a comparison, something like:
unsigned char* src_dest[] = { src, dest };
for (...; ...; src_dest[0]++, src_dest[1]++)
*src_dest[1] = *src_dest[*src_dest[0] == transparent_value];
the lead who reviewed the test had to come by and ask me to explain how it worked. Certainly, this was "branchless", even without the presence of cmov, since it was just doing movs based on a 0/1 produced by the comparison. But the actual source of the dependency here is the comparison, not a jmp or a cmov. The loop was faster than a branch on the CPUs of that era but these days it would probably be much slower.