On my version, it works correctly, so I cannot tell what the issue is.

After a little bit more of investigation - it happens for foreign (not mine) messages.

do you have something like alternating colors enabled? (incoming/outgoing messages in a different color)

Yes, I have it enabled as it helps a lot with readability.

But it leads to this issue, am I correct?

After disabling it search works well.

I've fixed the issue by disabling row coloring in the search dialog box