Seems it is an Encoder problem only, perhabs your does limit the frequence bandwith to much. For comparing I've uploaded the agony intro as mp3 in 128kbit to one of my webspaces. This tune is not the best gametune, even the original quality is shit for my taste, but compare it to your mp3 and you hear what I mean. MY example got a little bit more power in th heights, I did even not overwork it, you will hear some clicks here and there, but seems to be normal. But it is closer to the original.
In my opinion as I sayed only a problem of the Encoder, seems Lame standard settings are to underpowered in 128kbit, specialy the preset settings. Perhabs tweaking arround with the filters could bring a better sound, normaly lame is the best encoder, but without tweaking some filters it is not as good as weaker encoders without Band Filters, try that.