They can be reasonably sure they do not infringe known patents from certain Patent Pools and patents declared as part of MPEG-LA bundles. They can't provide reasonable data that they do not infringe on any submarine patent, something that killed 3 attempts by MPEG-LA to provide a royalty-free codec for the web - all that was required to kill it was a note from a company that they "might" have patents covering things they tried to release, or that they decided not to allow royalty-free license for their known patent.
Meanwhile patent search is complex enough that it's unreasonable to impossible to make a statement that you definitely don't infringe any unless you keep clear of anything invented within last ~20 years.
That's true of every new video codec. It didn't stop the use of H.264 or VP9 or even HEVC.
Multiple companies have now rolled out AV1 into production. We'll see what happens.
What's wrong is claiming that AV1, VP9, VP8 are "patent-free". They are not.
Care to try your luck?
I don't think they'll be successful. The Alliance for Open Media was careful to avoid potential patent problems during AV1 development. So, unless AOMedia seriously failed in that effort, AV1 will be alright.
The patent system was not designed to have every tiny little technique patented, and this is its failure mode.
In the USA. Wilful and unwilful infringement of the patent costs the same in Europe.