I'm just guessing, but I'd think that even a remixed instrumental version of a piece of music would still infringe the original copyright. Having said that, as long as you weren't offering the music for sale from your site, or on a peer to peer download basis, I doubt that you'd ever have problems. It's unlikely that your site would ever be found by anyone in a position to sue and, in the event that someone did have a problem with your use of their copyrighted music, you'd probably just get a formal warning to remove it to prevent further action.

www.flashkit.com/ have a selection of royalty free sound clips in various formats if you want to be on the safe side

Midi files are frequently used for streaming sounds because they are usually very small file sizes compared to some of the other formats. You could also look at streamed Flash audio produced with Macromedia Flash or a program like SWF Sound Automation Tool.

I hope that's some help!