Thank you for your reply. These options are the same exactly in my site.
I can see the issue – it is displaying posts, that belong to a different post type, first, and only after that the most relevant post.
Which means that even though it is not displaying the group headers, it is still grouping.
Is there another option that should be set?