Some of the songs in my collection have sounds that only play on one of the stereo channels. For example "Don't Let It You Down" by Spoon has all of the vocals on the left channel. This doesn't sound natural when listening through headphones. Does anyone have any solutions for songs like this?

Isn't that intended? I have a song by Aimee Mann with the drums only on one channel (also intended and I love it, because that's why we have things like stereo and 5.1, to have different sounds on different channels).
If you really want it, in xine (and probably also for other engines, I just know that xine+alsa can do this) you can switch to mono and you will get the vocals delivered to both headphones.

It's annoying when listening on headphones, because none of the sound will reach the other ear.

I had the same problem some times before and I don't actually know how to solve it, but  I think I have an idea what is going on. The audio is being played not through the L-R matrix (Left-Right) but through the M-S matrix (Mid-Side), where M=1/2(L+R) and S=1/2(L-R). In other words all the things that are normaly panned in the middle of the mix (like vocals or kick drum) are playing through left channel; and the things from the edge of ponorama (left or right - doesn't matter) are playing through right channel.

P.S. I have ECHO MiaMIDI soundcard so i had to compile ALSA drivers from source, so maybe it has something to do with ALSA, and maybe not.

Yes that could be a problem. Especialy with music that uses the stereo tool much, as e.g jazz often does. With speakers it dont get annyoing, as the sound "blends together" as it moves through the room and to you.
If you use xine you can change the Speaker arrangment. I was under the impression that if you chose Headphones 2.0 it would blend the two channels for you, to emulate what happends if you had used speakers. But I have not verifyed it.