Pretty much every method involved in high-efficiency video compression has a patent on it, doesn't matter how small part is involved.

Now compound this by the fact that a) trying to make an exhaustive patent search to get a verifiable claim that you don't infringe on any patent is very problematic b) known patent pools like MPEG-LA are known not to cover everything.

So you can make a reasonable bet that you avoid infringing patents by avoiding patents from MPEG-LA and few other better known groups, but you can't actually guarantee that you're not infringing on any patents.

This resolves, sort of, into a game of chicken and depends heavily on whether a lesser known patent holder decides it's worth it to bother executing against you... but even if they don't, unless they come out with a royalty-free license, the possibility of patent is a Damocles' Sword hanging over your codec.

"make an exhaustive patent search to get a verifiable claim that you don't infringe on any patent"

Is there even such a thing?

Isn't the problem that one has to actually go to court to get the answer to this question?

In theory you can do such kind of search. Problem is that doing that is impractically expensive (and at least in some jurisdictions doing that can actually raise your liability in case of patent infringement).

Does such a search indemnify one of liability though, is the big question?

No.

In fact, I heard more than once that current advice is to explicitly avoid searching :/

Because there are companies with a lot of money in this space which spend all their time trying new things and patenting anything they come up with, even if it doesn't make it into a published codec, basically.

The way to get around this is to exist in the EU and avoid providing anything to the US.

The field is littered with companies holding submarine patents just waiting for that big payday when something using some tiny part that they patented gets popular and deployed to millions of devices so they can surprise everybody with their pricey licensing terms and huge lawsuit.

It would be hard to build a new algorithm without stepping on other established algorithms that are patented.