|1 - I would make people prioritize the records they want - only 1 number, let's say, from 1 to 100.
2 - They would then choose the records they want, in the rank they want. Not allowed to repeat numbers.
With that information, I would assign a priority value for each ranking, the higher the priority (1 is highest), the higher this number is. The balancing of these values is going to be a big part on your "justice".
I would do a cumulative priority number, and upon collision, the person that asked first for the record would get it.
Let's review this, in a slower way:
Let's say you use 1 => 400, 2 => 200, 3 => 100, 4 => 80, 5 => 70, 6 => 60
Now we have the first choice round. Everyone gets 400 priority points. Let's say 5 people.
But there is a collision. 2 people chose MC Hammer record.
The one that asked for it before is going to get it. The other one... well, tough luck.
Now, we have the second choice round. Everyone gets 200 priority points.
But, the "un-hamnmered" guy now has 600 priority points. Whatever he chose for choice 2, if available, is going to get picked.
After that, everyone else can get their choice of number 2, if available.
Just repeat until no more records. This should be a fairly fair system - everyone is probably going to be equally pissed... lol... You are seriously underestimating human beings' capacity for being petty - I hope all goes well, but I really think you're going to have some headache.