Honest question: What happens if a Russian or Chinese search engine doesn't comply?

How would the EU block them? This is especially important if the Russian or Chinese entity has no locus or presence in Europe.

(for instance, would you be able to get around it using a different DNS, or by using a VPN?)

They'll just block payments to those sites. You know, from the advertisers - the actual customers of the platform. No one cares what people use for free. This is about money.

Russian Yandex is incorporated in Netherlands, which is a founding member of the EU.