How about adding a field for each song whose value is the maximum score possible. Then you can just make a little PHP script that is scheduled to run every hour or so with the following:
$songres = mysql_query("SELECT maxscore, songname FROM songs");
while (($songrow = mysql_fetch_assoc($songres) !== false)
{
$songname = $songrow['songname'];
$maxscore = $songrow['maxscore'];
mysql_query("DELETE FROM scores WHERE songname = '$songname' AND score > '$maxscore'");
}
mysql_free_result($songres);
That'll at least stop the *obvious* cheaters.
$songres = mysql_query("SELECT maxscore, songname FROM songs");
while (($songrow = mysql_fetch_assoc($songres) !== false)
{
$songname = $songrow['songname'];
$maxscore = $songrow['maxscore'];
mysql_query("DELETE FROM scores WHERE songname = '$songname' AND score > '$maxscore'");
}
mysql_free_result($songres);
That'll at least stop the *obvious* cheaters.

Comment