Having said that, the accounting doesn't have to be that complex:
1. When paying out an artist, list out the (anonymous) users who listened to their music on Spotify.
2. For each user:
a) Show the what percent of the user's total listening was spent listening to that artist. (e.g. 40%)
b) Multiply the amount the user paid by the percentage from (a). (e.g. $10/month * 40% = $4)
3. Sum all of the amounts from #2. (e.g. $4 + $3 + ... = $total)
Also, accounting would only be a problem for Spotify. 99% of artists would prefer this model, even if it meant more complex accounting.