The following should be fast, it allows arbitrary large files, and it preserves order:

perl -ne'print "$.\t$_"' input.txt \
   | sort -k 2 \
   | uniq -f 1 \
   | sort \
   | cut -f 2- \
   > output.txt
[download]

• Prefix each line with its original line number,
• sort (ignoring the prefixed line number) to group duplicates,
• remove duplicates (ignoring the prefixed line number),
• restore the original order, and finally
• remove the prefixed line number.