If you click the "Preferences" link on the front google page, there's an option called "Format". By default, this is set to HTML, but there's an option for XHTML. If you choose this, the layout which results is what you're describing. The reason clearing your cookies worked is because it removed the previously stated preference for Google to display in XHTML rather than HTML.
On a sidenote, I find the XHTML layout to be exceedingly worse than the default HTML, does anyone actually like it more?