I don't want to bog down the lyrc.com.ar servers, but
perhaps you could send the difference between a
person's current playlist and the already downloaded
files in ~/.lyrics/ and automatically download the
remaining song files that only have one possible entry.
Just a thought.