I'm not using random battles, but I ran into a similar problem. I think I tried removing the battle music and all that did was give me silent battles and the BGM still reset every time I left battle mode, though I may have done something wrong.
If anyone has a good work around for this, I'm interested as well.