If you have modified the ItemStyle.xsl file (located in the Style Library) to change the way the Content Query Web part looks, remember to check it back in and publish a major version for anonymous users to see the changes.

I hope this post saves someone a couple of hours of hair pulling.