Baxslash, I have the same argument - with the MP3 license, not with anyone in particular!
I emailed them long long ago and they admitted that Microsoft already paid the license fee for MP3, otherwise they couldn't distribute DirectPlay - so they already paid, and now our software plays through DirectPlay and we are expected to pay again!
Personally, I don't think the license holders have a leg to stand on - you can't even protect an algorithm in the UK with a patent, so the license for it in the UK at least is pretty much worthless. I'm sure it would be quite easy to beat a court case with any reasonably astute patent lawyer as back up.
Just picking holes again but...
* How do they know you've distributed >5000 copies - I can't say for sure how many copies of my games are distributed, heck I'm due them an absolute fortune if I believe everything on their site.
* How can they ever hope to win a case of free software violating their license!, no judge would touch it with a barge pole. No income = no court case. A game would have to be big and profitable before they'd ever raise an eyebrow.
* How can they charge for a license to distribute an algorithm that you don't distribute! - what part of an AppGameKit app has all the MP3 replay code? - DirectPlay?, OpenAL, whatever - we don't distribute, it's not our responsibility, and the license has already been paid for. The crux of the matter is the fact that we don't distribute the algorithm, so what is the license for!
But we have to remember, patent's don't last forever, the MP3 license patent will expire in a couple of years I'm sure, so the holders are just trying to maximize their reach. We consider what the heck we are supposed to do... well I'm not changing anything other than taking the advise posted here and just avoid using MP3 wherever possible in new projects. I would love a face to face with a patent lawyer though, I might not necesserily win, but I'd have the most limbs left by the end of it.

I am the one who knocks...
