OK, so the answer is that you want it back for the sort status and ease of changing sort order. I can understand why some folks would want it.
However, I don't think that this feature should be provided by violating the guidelines of good usability and interface design. The column headers are shown in the Details view because it is tabular data. The Icon views show thumbnails in a grid. It does not make sense to show tabular column headings when viewing a grid. While some people might like it, most people would find it confusing. Also, a usability review would consider how often people change the sort order of their thumbnails and probably conclude that it's fairly rare and saving one mouse click per operation is hard to justify.
Still, I would support the idea of an optional sort status indicator and changer that followed the design of the rest of the view. So, an icon or series of icons or button(s) on a toolbar would work. For some reason, this is not a common feature in thumbnail viewers, even dedicated ones. I took a quick look at a few -- Picasa, IrfanView, FastStone Viewer 3.5, Canon Zoombrowser EX -- and none of these provide an easy to see or change sort options. At least, not that I could see with a quick look. However, Windows Live Photo Gallery does provide exactly this kind of sort status view and modifier:

Notice that it shows the current sort status, "Auto", and the order, "Ascending". Clicking on the sort order button changes the sort order. Clicking on the sort category shows a menu of other categories. This is an example of what I was suggesting before of an application with a narrower focus (image viewer) and more features than the general purpose Explorer.