Just found this article by Mike Gehard which shows a good step by step of making a content query web part look like a grid - with column headers and all.
Mike is even using the same ddwrt trick as I am for formatting dates, and I now see that his blog seems to be dedicated to the content query web part!
I recommend you go to Mike's blog and read all about it. The method he is taking is chaning the "ContentQueryMain.xsl" file to pass the lastrow as a parameter to the "CallItemTemplate", and then in "CallItemTemplate" he passes the lastrow to the apply templates itemstyle.
In the "Itemstyle.xsl" file you add html variables for the header and the footer, and use them before the first row and after the last row.
I will try to contact Mike and ask for permission to reprint his article here for redundancy.
Mike - if you are reading this, how about you join the Enhanced Content Query Web Part project?