Which phone?
Which version of android?
which carrier?
Which message type (SMS/MMS, email, instant message)?
Which messaging app?
The orientation data is contained in the EXIF data of the image. Some apps may remove this data to make the file marginally smaller for transport. Some online services also remove this data.