You may find that no technical solution is suitable for a karaoke web site. Typically such systems look for specific versions of a song, rather than what is essentially a cover of another musical composition.
A simpler option might be to put this clause in your T&Cs, and then reactively moderate uploads based on reports. Make reporting alleged copyright violations easy and respond quickly, but beware of false claims too.