I fully agree with topo's answer, though on many occasions I've known a remix to be done initially without any permission, just to see if the track will gain any traction on the dance floor, as a white label.
Only if it does see some good feedback do the record company then go to the copyright owners for permission, based on the 'if it doesn't sell, no-one will care' assumption, which lawyers may argue over but is usually not worth the effort.
I've then known for the original 'borrowed' samples to be re-recorded to save having to pay the full royalty for the usage, instead only having to pay some smaller amount for a 'sound-alike'
In one specific case, after doing the re-record, the remix artist was then tasked to 'remove all copyrightable elements' of the re-record - by subtly changing chords, melody lines etc - until only the hint of the original track remained, yet enough to still give the feeling that it was the inspiration for the part.
Case in point - Inaya Day - Nasty Girl
The final release is a complete re-create, with changed structure - sufficient to keep the lawyers happy.
The original dance floor release contained samples of Michael Jackson's 'Don't Stop til You Get Enough' which was later cleared for use with the copyright owners, but not used in the hit single release.
Source/disclaimer: personal experience, I know the creators of the track & how the negotiations were done towards the final release version.