When moc starts it launches two components, you can see them in top or htop. So, there's a daemon and a client. When you close the client with 'q' or you exist X or close the terminal you run moc on, only the client is closed, the daemon still exists in your user space. Which is why the playlist remains running even when you have closed moc.
To completely exit moc you need to use shift+q instead if my memory serves well.
My -wild- thought is that maybe you closed only the client, but not the daemon, which means that you were still using the old moc that was living in your ram which had no support for libmad. Maybe then you closed moc entirely and after launching it again that was the new one, which worked with mp3's without a problem.
i92guboj, 'revdep-rebuild' is not working. It says command not found. What package I need to install?