I am not sure which payment model I prefer, but I don't buy the technical reason against the OP's proposed solution. I imagine Spotify already maintains a list

I am not sure which payment model I prefer, but I don't buy the technical reason against the OP's proposed solution. I imagine Spotify already maintains a list of songs played by each user (to build their recommendation engine). You could report to the artist using a histogram (bucket the listen by the percentage of user's listens they represent). Also, Spotify could build a nice web interface that allows artists to understand their revenue stream, with various aggregated stats and graphs.