You're right - those pages WERE doing OK without H tags. Many pages from many websites hold on to a tight #1 position without any H tags at all. It's still not the best practice.
Not only that, but people do use other search engines to look for pages on google.com - it happens all the time. The major search engines have all been at least somewhat attentive to their own in-house SEO for years. So this Google initiative did not really surprise me all that much.