Some of the first comments submitted in this thread suggest to me that it may be helpful to review the various convergent lines of evidence for macroevolution, which along the way will help explain how biological evolution works and why very old "complexity" is not a surprise in the fossil record. (One problem is defining "complexity" adequately in this context.) See the very informative collaboratively edited website 29+ Evidences for Macroevolution: The Scientific Case for Common Descent[1] for the broad overview, and specifically the sections responding to "complexity"[2][3] for more details on that issue.
Arthropod was supposed to be the next word of the title, but understandably, the author of the piece was short on time. The article's about the fossil of an ancient great ancestor of shrimps. The fossil has spectacularly well preserved impressions of soft tissue.
Evolution is not a relentless forward march, and if it could have inclinations, streamlining its productions would not be one of them. Doing so only when necessary, in cases where replication is also somehow advantaged. Usually... http://c2.com/cgi/wiki?ItAintBroke
I'm always surprised how people describe evolution as from a source information independent from fossil evidence. When, in fact, we tell what evolution was, up until now, from the evidence we have and not something else. The evidences shapes the theory (the sum of theories). If complex organisms become simpler, than that's how evolution works. If simple organisms become more complex, than that's how evolution works.
Epistemically, what's going on, I think, is that evolution is pretty much assumed to be true and from the evidence it's only concluded what results it had.
There is certainly no forwards and also no backwards. It is just an on going optimization process. It is on going because the constraints change. Most of the constraints can be summed up under the general term "environment". The effects of the climatic environment can be grasped more easily. However it is harder to grasp how all(or most) of the constraints feeding into each other, across both time and space.
With that said, life as we know it has a penalty on needless complexity. And, what does complex mean anyway? Complex genotype or complex phenotype? What is a good metric for measuring each one? Whatever the metrics are, it cannot be said that they are related monotonically. In this sense, we have four permutations of complexity i.e.[simple genotype, simple phenotype], [simple genotype, complex phenotype], [complex genotype, simple phenotype] and [complex genotype, complex phenotype]. Life as we know it is defined in the whereabouts of the genotype level. The "penalty" is on the [complex genotype, complex phenotype] type of complexity primarily because of the inaccuracy in the cell division process/processes (life as we know it!!). With many points that can go wrong in the foundation(cells->chromosomes->genes -- genotype), you don't want many points that can go wrong in the outcome(phenotype).
Of course life can (and does) beef up the genotype level with more complexity to try and ensure a rock solid phenotype (complex or not) but all factors withstanding, a simpler phenotype is easier to maintain.
The evidence shapes the theory, but the theory also shapes what we can understand from the evidence. As well, the fossil record is not our only evidence. When people describe evolution as a thing independent from the fossil evidence, they mean "The things we've learned about how evolution works." It's not really independent of the fossil record, but neither are they one and the same.
Similarly, people talk about physics as a mathematical field, even though what actual entities do in the real world is the only real source of information. It isn't that the real world can be "wrong," but if a piece of evidence doesn't fit with our accumulated knowledge, that needs to be explained, not just accepted.
I call this "Science of the Gaps". Where there is insufficient evidence to reach a conclusion, or to provide a mechanism for a process we know occurs, one is just made up (by non-experts seeking to bolster the image of science).
My understanding is that no one knows how life originated, but that doesn't stop many people from prematurely invoking the Anthropic Principal.
On complexity, logically, we cannot say that evolution has no tendency towards complexity, and also that evolution explains the complexity of modern organisms. Not that the OP was making the latter claim, but it's not an unfair assumption.
Also, your post seems to suffer from "feigned surprise" :-)
Interesting and weird! It's similar when studying the evolution of the horse! The legs went from quite a few complex moving parts down to a much smaller number in a simpler configuration in the present day. http://en.wikipedia.org/wiki/File:Horseevolution.png
This is from the http://en.wikipedia.org/wiki/Maotianshan_Shales at Fuxian Lake, Yunnan, China, which is where I live. In fact, I have friends who work in the geopark. If anyone's ever out here it's well worth a visit, with 3D models of various bygone critters and loads of fossils to look at, complete with magnification equipment. The lake which the fossil is named after (despite the temporal disparity!) is the second or third deepest in the country at 400m, 20km long, and resting at an altitude of around 2000m, and surrounded by pine forested mountains and archaeological sites of the https://en.wikipedia.org/wiki/Dian_culture. Not a bad spot to ponder timespace.
Evolution allows unneeded features to fade away. My gills, for example, are almost completely gone. Specific complexities evolve when they serve a purpose and recede when no longer needed.
Agreed, just like how languages evolve to become simpler (faster and easier to speak), evolution should cause anatomy to simplify and become more robust to adversity over time.
"We also used the Adobe Photoshop CS5 to manipulate the images in order to extract further information." Can't believe they admitted to tampering with their scientific results in an image editing program ;)
[1] http://www.talkorigins.org/faqs/comdesc/
[2] http://www.talkorigins.org/indexcc/CI/CI101.html
[3] http://www.talkorigins.org/faqs/behe.html