My vote final vote is for a koi (amur river carp).
I did a little research and was surprised to find there are lots of different colorations, having mostly seen the orange & white and black varieties. To me the fish third from the left has similar colors:
According to wikimadeuppedia, they are supposed to revert to more natural carp colors if they are released into the wild:
Quoting from the article:
"Koi have been accidentally or deliberately released into the wild in every continent except Antarctica. They quickly revert to the natural coloration of common carp within a few generations. In many areas, they are considered an invasive species and pests. In the state of Queensland in Australia, they are considered noxious fish."
My guess is that someones koi pond got flooded in Sandy or Irene, and this is one of the illegal immigrants who made a run for it. The damn things like most carp can live to be 150-200 years old.