I just did some tests. Yeah, Landscapes seem fine which is why I never noticed this. I take 99% Landscape photos.
As for Portrait, they come out good in some places and bad in others. After e-mailing:
Portrait Shows Correctly:
Online Web G-Mail's Preview Thumbnails
iPhone's Photo gallery
iPhone's Mail App (using G-Mail)
Mac OS X (Finder, Quick Look)
Mac OS X Preview application
iPhoto
Portrait is Rotated Sideways:
Online Web G-Mail's Full-Size View
Windows Explorer thumbnails
Windows Picture Viewer
Final Cut Pro
Quick Time Player 7 (Mac version)
So this is NOT an issue of the information not being recorded in the photo. Some programs can see it correctly!
But clearly there is some kind of bug. I'm not sure why some things get it and others don't, but it's not the same everywhere.