I wrote that original code on Stack Overflow, but I didn’t see your further replies because you posted them as answers and not as comments to my answer. I have tested the code now with a specific category and it works for me, but it needs one crucial change: the call to the_post() (which I completely forgot) must come right at the beginning of the while ( have_posts() ) loop, otherwise the year will always lag one post behind. I have corrected that in the original answer.
If you want to specify multiple criteria for your query, you must combine them in the same function call. So not query_posts('cat=27'); query_posts('nopaging=1');, but query_posts('cat=27&nopaging=1'). You can also use the array format (as in my original example), I prefer that for readability.
A last change: if this is not the main loop of your page (and I suspect this code will end up in a sidebar, so not the main loop), [it is better not to use query_posts()][2]. Instead, try get_posts() and use the result of that. I did not know this when I wrote the original answer, but hanging around on this site learns you a lot!