There are plenty of legal open source H.264, MP3, etc implementations. AFAIK source code license and patents are orthogonal concepts. You can use any source code, proprietary, open source or written by yourself, but you should have permission from patent owners, because you're likely using their patented algorithms.

So, to produce a legal open-source (as in "free to reuse and fork") implementation, the implementor would need to obtain a permission from the patent holders, and make sure it covers all the possible derived work?

Is this known to have ever been achieved?

It's not about writing code, it's about using algorithms. If you're using MP3 algorithms to make money selling phones, you have to pay a fee. If you're using MP3 algorithms to make money selling your WinAMP player, you have to pay a fee. Whether you found implementation on github or read patents and implemented it yourself, does not matter. I don't think that you have to obtain a permission just to write implementation out of curiosity, but I may be wrong. And I have no idea about status of open source projects which include patented algorithms, but distributed free of charge. Probably they can't do that, because Linux distributions did not distribute mp3 codecs by default.

Also all of this is applicable to countries where those patents are working, of course.