[Presto]

Can anyone recommend a decent sound editing program that can remove vocals from songs?

[Manic!]

It really can't be done. Best bet is to find the instomental.

[pokchop]

there are many sound editing programs out there but the result will never be perfect... a program you can try is Adobe Audition...
some songs have better results then others as well... really depends on the singer's voice and song's music... and there are notes throughout the song that are going to be missing after you remove the vocal :s