I imagine this may have seemed innovative in 1995 to the patent examiner at the time seeing as the internet was brand new and music was still on CDs but do we want to really reward the genericness of this patent and stifle innovation?

Here’s the abstract from the patent asserted by PacketVideo against Spotify:

In order to distribute music information from a central memory device (2) via a communications network (4) to a terminal (6), this information is organized in a digital music information object. The latter comprises a core having basic information relating to the music information object, as well as a number of additional layers having the actual music information. The core includes an encryption table, on the basis of which an encryption module (30) of the central memory device (2) and a decryption module (32) of the terminal (6) respectively encrypt and decrypt the music information object. Furthermore, an interpretation module (34) is provided in the terminal (6) for reproduction conditioning of the music information object, which interpretation module (34) accesses information for checking the authorized use of the music information object, which information is stored in an authorization device (36) and identifies the terminal or the consumer. The invention thus creates a technique for distribution of digital music information which on the one hand provides effective mechanisms for the protection of copyrights and on the other hand makes possible increased services for the consumer.

5,636,276

ZDNet has the relevant legal papers.