This isn't a problem for Google. They can pay the patent, and in case they couldn't, then they can change the codec they use in a very short timeframe because they've the resources to do so.
It is a problem for small developers, though. The motivation behind patents is protecting individual inventors. But it's become the opposite: a market for buying and selling IP, where none of the parties have nothing to do with inventors.
Patents should be bound to the income generated by the product. If a product is free, patents should be allowed to be used free-of-charge, provided that the name of the inventor is acknowledged, and the patent is mentioned in the product info together with the inventor's name.
If the product isn't free, the patent should be payed as a percentage of the product income, to the inventor. Never more money than the generated income, as this would be nonsense (patents are meant to protect the inventor, so that he gets the benefit that the patent produces, and not more benefit... it's nonsense to pay more than the benefit it generated).
Patents shouldn't be transferable. It's nonsense to pay a royalty to somebody who didn't invent the patent.
If patents were like this, their real motivation would be guaranteed.
This would be perfect for Google who like to give everything away and get income via ads. Don't see a problem here?