Not actually a fix to your code, but a slightly different approach, would be to temporarily store each FASTA record in a hash using the complete header as a key. This way you can check for existence of a known header and print out the records together.
I haven't tested it, but the problem you are getting looks like it could be a buffering issue? If you ++$|; # turn off buffering, the issue might go away, but I still think i would go with the hash approach as it doesn't rely on the records being in the same order etc... HTH
Just a something something...
