The problem with compressing mp3s is, that WC3 is only able to read certain parameter combinations (sampling rate & bit rate). If your compression is between those combinations, the lower one is selected, making your audio even worse than in your compressed file, so make sure you don't compress it into oblivion.
Even if it hurts: I recommend getting rid of custom music at all.
In the end, a lot of people will switch it off anyways, for several reasons (one of them being that they want to listen to their favorite bands instead. I do, at least).
Also, WC3 doesn't support other file formats that compress better, like .ogg.
I started removing the music files now for the newer releases of Gaias because of that. Next version will probably come without any custom music at all. It's simply not worth it. I also removed the loading screen for the same reason (too much file size for just some seconds before the game starts).