Is Ghengis Khan the reason it's so hard to find blue-eyed brunettes in Eastern Europe?

The real question is whether in fact they are over-represented even in photos. You haven’t provided any objective evidence that they are, merely your assertion.

What search terms are you using?

If you overlay the one on the other, the one place in Russia where (relatively) dark hair seems to overlap with light eyes is that darker-hair salient in western Russia, just east of Latvia and north of Crimea. If I read the map right, that would be Tver Oblast, northwest of Moscow. So the OP’s chances might be improved by narrowing searches to ladies of Tver.

Anyhow, Elemenopy is right: your best bet for that combo in all the world has to be Ireland.

Can you stretch your definition of “Eastern Europe” to include Greece? I’ve met several Greek and Greek-American women with blue eyes and dark hair.

No search terms. I have a number of “TGP” sites that I visit regularly, where many/most of the models are Eastern European. I’ve also looked at a number of subscription sites based out of Eastern Europe. Brown eyes everywhere.

I’ve found one look that I really like, though I’ve only come across it a handful of times: Dark brown/black hair, dark olive skin, and … greenish-grey eyes. Think of that Afghani refugee girl from that famous National Geographic cover. I’ve seen this look on a very few models from Russia/Ukraine, so I assume their ancestry comes from further East. It’s a striking look.

Try
these.

Loads of blue-eyed brunettes and a few blue-eyed redheads in my family.

Risking being whooshed, black Irish is the term for an Irish Protestant.
My brother, who is a blue-eyed redhead like our mother, told me that red hair and blue eyes is supposed to be the rarest combination in the world according to an article he read. I find it a bit hard to believe because every redhead I’ve met except two have had blue eyes and the other two have brown, (well, I’m a redhead too and my own eyes are blue enough to satisfy the DMV but might technically be hazel because they have brown rings around the pupil and change to green, gray, and combinations of blue-green-gray) so it feels like red hair and green eyes are rarer. If it’s true, though, you’re not going to find a lot of pictures of blue-eyed redheads regardless of where they live.

I’m Irish-American, and I don’t believe I’ve ever heard that definition. “Black Irish” simply means an Irish person with black or at least very dark hair. It varies whether the eyes need to be dark as well. The legend is that this trait descends from survivors of the Spanish Armada who were shipwrecked in Ireland and welcomed as enemies of England.

The Master speaks on the Black Irish.

Spanish Armada survivors in Ireland.

I noticed when I was in Paraguay there were quite a few dark haired people with blue, green or grey eyes. I figured it was due to European immigration intermixing with indigenous people, but I’ve never cared enough to investigate it. It could be quite striking, though.
How about dark hair, blue eyes, and freckles?

“Black Irish” has no real currency in Ireland but the term black is (or at least was) used to refer to Protestants. “Black Protestant” is a term I’ve heard in the north many a time, I’ve also heard the term “black bastard” in a sectarian context and the term the “Black North” is/was used to refer to Northern Ireland. The Black North - Wikipedia