Headphoned is application that you can install from extras testing. It pauses mediaplayer automatically if headphone plug is taken off while listening music.

Does this random pausing happen while phone is in pocket? Does it happen with all songs? (like are you using mp3, ogg, flac or any other format?) Have you installed anything that might be incorporated with mediaplayer (like codecs, or any experimental devel&testing stuff). Does songs pause while listening with headphones and also when listening trough speakers.