Last I looked, neither fedora nor mandriva (your examples) support restricted formats
out of the box.
The commercial version of mandriva includes mp3 support for which they have paid a license, they expect you to pay them in turn.
The short answer is:
Distros do not include some things because it is illegal for them to do so. Some distros include these things for pay - under license (which is legal). Some distros include these things because they are not concerned about complying with some laws.
Most major distributions do not support restricted formats because this would expose them to litigation, which could threaten their free-of-charge nature. Technically they are offloading the risk to the user - if you did not pay a licence fee for your linux mp3 player, you may be breaking the law.
Some distributions (Mint, Mepis) do supply restricted codecs - presumably their developers have decided to take the risk, or they live in countries with more liberal laws.
Some distributions refuse to support restricted formats/codecs for idealogical reasons - part of the whole point of using free (as in speech) software is the freedom itself. The idea is to expose users to ideas about free formats, codecs, and freedom as it applies to software, so that they are able to make an
educated choice about their computer use.
In the case of music, far too many people think that "mp3" is
the same thing as "music".
Installing an mp3 player is not onerous. Instructions are available to anyone prepared to google "OpenSUSE mp3". Someone not prepared to google this, or unwilling to do a short additional install, will probably not be a good community member, so they are welcome to go to a less-free system.
For more information:
http://www.fsf.org/resources/formats/playogg
http://www.openformats.org/main
http://en.wikipedia.org/wiki/Open_format
Here's an example of mp3 royalties:
http://mp3licensing.com/royalty/software.html
An example of mp3 patent enforcement in the news:
http://news.bbc.co.uk/2/hi/technology/5312696.stm
