Within sampling, the rule of thumb that I use is if someone can recognise the original song you've sampled, then you should probably get the artist's position. On the other hand, if you've used tons of samples and really messed about with it creatively, then I don't really count it as using someone else's work or talent to replace your own, since you're putting in just as much work and talent.
I'm aware the above is just my opinion. It wouldn't hold up in court, I'm sure
Also, I love the remixes on that page you linked. The 'No One Knows' one is ace!