Please have a look at this (I'm speaking about cold play first release.)

All I can say is that he bought it in Piccadilly records in Manchester a long time ago (1998)before they became very famous . At this time he was living in England and used to go once a week to that store .500 copies **had been released** not 50 or 500 copies **were released** not 50

Which solution is the best?

I think the first one past perfect is the best because first the record was released then he bought it but it seems evident that you can't buy a record before it is released so past simple might fit too.