EU, UK
Neither of these allow software patents (despite what the European Patent Office might tell you). Germany does unfornatually but they're not the EU in the same way the UK isn't.
Actually, the wording is closer to "software patents as such". I.e. "software which improves the operation of a computer, but does not necessarily have an external effect, is not excluded from patentability." (from http://www.cellular-news.com/story/35181.php )
That means you can argue that a patent that improves machine performance is legitimate. You could argue VP8 patent-ability hinges on whether its faster in area of application than H.264. Slower, and you can't argue machine performance versus peers, and you get no patent.
Plenty of room for an evil genius patent drafter to write a patent that narrows the domain of application to places where H.264 doesn't run or H.264 runs more slowly.
"Experience has proved that some people indeed know everything." -- Russell Baker