Google have published some news on sitelinks on their blog - introducing the new one-line sitelinks, and confirming that these can appear in any part of the results page - not just the top spot. http://googlewebmastercentral.blogspot.com/2009/04/one-line-sitelinks.html
Yep, in fact it seems they are very common already. I see one-line links very often during my searches. It's a cool idea, promoting what the search engines think are more important or relevant internal pages. This way you can see if you're doing your SEO job right too
That is pretty cool. I had not noticed this before your post, but I am happy to see that one of my sites now has site links on many of the search terms, not just the ones where it is in the #1 spot.
That's great, apart from SEO, these sitelinks will help users to go directly to the required page and will make their google search experience wonderful.
I think I like the two column version better. But I can also see where the single column has its benefits. Hopefully this will get deeper pages to where the public can see them from the google search results.