Can you come up with a canonicalization for all these fields? Even if you can't keep them in canonical form, that would basically solve the immediate problem.

Let's say, for example, always sort them so $1 is alphabetically before $3. So swap any fields where $3 is before $1, then sort -u and all that.

Code:

awk '$3 < $1 { t = $1; $1 = $3;  $3 = t } { print }'

Extending this to keep counts for each canonical form in awk itself should be fairly trivial.

Code:

awk '$3 < $1 { t = $1; $1 = $3; $3 = t } { a[$0]++ } END { for (k in a) { print a[k], k } } '

Addendum: If you have additional fields you need to key on just $1$2$3 instead of $0, of course. Then you can't keep them in the weighted summary, though.