I am curious to know why is sort (the unix tool) not working? If the file is unsorted (on the composite key) and you care about the order of the lines, why not add the line number, sort -u on the key, sort on the line number and then cut the line number?

If the problem is getting the key using the admittedly obscure sort options, you can have a perl (or awk, or whatever) script gather the complete key and add it as an extra field on each line, so that sort can find it easily. Incidentally, this is very similar to a Schwartzian transform.