Geralmente utilizo o comando sort para remover linhas duplicadas de um arquivo:

$ sort -o output -u input

O problema era que em alguns casos as linhas não poderiam ser ordenadas, mas o sort (obviamente!) as ordenava. Então acabei resolvendo o meu problema assim:

$ perl -ne '$i{"$_"}++ || print' < input > output

O mesmo pode ser obtido via awk:

$ awk '!i[$0]++' < input > output

Ou:

$ awk '!($0 in i) {i[$0] ; print}' < input > output

Sendo "input" o arquivo de entrada e "output" o de saída.

Falou! ;)