SuperSearch (done already - here's the link: ?node_id=3989;BIT=FASTA
-- will give you a short list of recent discussions on dealing with FASTA files.
My notion that your paragraphing might be identifiable with a regex is pretty useless here. However, there's no reason you can't read a 2 lines at a time and use hashes to ensure the two "neighbors" values are discrete.
That too, however, breaks down if the dups appear other than adjacent to one another, given the size of your data.
So if none of the above help, you may wish to read about bioperl at both the wikipedia article, http://en.wikipedia.org/wiki/BioPerl and at the project page, http://www.bioperl.org/wiki/Main_Page.