So, what is the law when it comes to doing a remix?
It's pretty cut and dry: unless the copyright holder on the performance has licensed it under a remix-friendly license like the Creative Common's license that allows reuse of the work, you're going to need to seek out and obtain permission to use any portion of the recording (even as little as three notes) before you distribute your remix. Note distribute and not sell in that sentence. Doesn't matter if you're giving it away.
Do i need to ask permission?
Yup. And you may need to pay to use the stems. There's no set rate for samples, the copyright owner can charge you as little or as much as they like for you to use the pieces of the recording. And they can block your ability to redistribute it if you use it without permission. For an interesting case in history see The Verve and their Bittersweet Symphony sample that cost them all their revenue on that track. In a similar fashion, Danger Mouse' Grey Album has had a cease-and-desist issued against it by EMI for its unauthorized use of Beatles tracks. I mention the last one because it's obviously prescient to you: Danger Mouse gave away the Grey Album. Whether you attempt to generate revenue or not, the copyright owners would still like to be paid for the use of their recordings.
It's tough to clear samples. From this Wired interview with the Beastie Boys done in 2004:
How do you clear the samples?
DIAMOND: It's very tedious. We have to sit there and basically break out every single component of every track that we do and make a list of the sources for everything. We go through every little blip of sound and decide what's significant enough that we need to contact the owner. From there, it's a whole bunch of lawyer craziness.
Here's an article from Keyboard Mag that talks about how you go about clearing samples. And a similar article from Sound on Sound that's also a great read. It all really depends on who owns the copyright. Start with the label and they should be able to direct you to the company that holds the rights on the samples you want to clear.
There are services like SCORRCIO that exist to recreate any portion of any song you might want to sample, at a cost that's hopefully lower than using the original. Since it's permission to use the recording that you're seeking (you don't need permission to record a song, but you do need permission to use a recording of a song), SCORRICO skirts around this by actually re-recording things and licensing that re-recording to you.
The fine print: I am not a lawyer, nor do I play one on TV. Please do not take this as legal advice, that which I am not legally licensed to offer.