This is a common misconception…
sampling of any kind could breach copyright
The term used is usually 'infringes' but the true statement is
sampling of any kind does infringe copyright - unless licenses are obtained.
There's no grey area in the copyright infringement. If someone finds it they can sue for it. The chances of them doing so are really proportional to the amount of money they'd make back from the action. A bedroom sampler with a couple of hundred hits on YouTube - no-one is going to bother.
There's no "You can do it if it's shorter than x seconds". That's a myth.
So is claiming "fair use".
There's a good quote in the linked article -
“We were definitely guilty of harboring a ‘No-one’s going to listen to it anyway’ sort of attitude.”- Robbie Chater
By implication, they didn't think it was going to go big time, so they thought no-one would care.
There's also this
"According to Chater, original drafts of the album had almost twice as much music as the version released to stores. “I think that the album was a little diluted by the time we had finished clearing all the samples,” Chater told Tiscali in a 2002 interview. “We’ve got even longer versions of the album back at home. They’re about two hours long, but we thought we’d better edit it before we put it out.”
So, yes, at some point someone had to go through the whole lot & apply for licenses. The ones they couldn't get had to be left out of the release.
You need two licenses to use a sample, one from the owner of the song, the other from the owner of the recording. These are not necessarily the same company, though they may be subsidiaries or partners. As the structure has become better organised over the past 20 years, companies now have departments set up to deal with this, making it easier than it used to be. However, unlike making a brand new cover version of an existing song, the license holder is not compelled to grant the license. They can just say no.
What does sometimes happen is that a track is released as a 'white label' - a theoretically anonymous track that's hard to trace back to the makers - to see if it gains traction on the dancefloor, before going for approval.
This happened to some friends of mine, who first produced this as a white label & includes several samples of Michael Jackson's 'Don't Stop til You Get Enough'.
Which, after some legal wrangling, licensing & re-writing was eventually released and became a world-wide hit as this
Another example - this one was never in fact released - we first got permission to use large chunks of the original Adamski/Seal track [three licenses, two independent authors for the song and a record company], which was used for the initial remix [no copy available], though eventually all was re-created from scratch, so only the song license was needed, the music itself was entirely new - a cover version, if you like. [I don't own the rights to this even though it's on my Soundcloud page. I did all the instrumentation & made the composite edit/remix.]
Tunecore: Music Sampling and Beat Licensing 101
DIYmusician/CDBaby: How to Legally Clear Samples to Copyrighted Music