Submarine patents are irrelevant. I.e. potentially anything can be patented by some unknown patents, and therefore by this definition everything is proprietary altogether? It's not how the definition goes however. If there are no known patents that cover some open source technology, it's free and non proprietary, until proven otherwise.
VP3 was originally encumbered indeed, as well as VP8 by the way.
So Theora based on VP3 is by all means a FOSS and non proprietary codec...
Theora is derived from the proprietary VP3 codec, released into the public domain by On2 Technologies. It is broadly comparable in design and bitrate efficiency to MPEG-4 Part 2, early versions of Windows Media Video, and RealVideo while lacking some of the features present in some of these other codecs. It is comparable in open standards philosophy to the BBC's Dirac codec.