"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?
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.