I've heard that the word originated in the Japanese Imperial Navy.
The abbreviation theory for "ohayogozaimasu", "onegaishimasu" etc don't seem out of place, particularly in a military/nationalist setting. (Apparently the Takushoku University Aikido club also used the word)
There is a page dedicated to the form and function of the word in Kanazawa's SKI Kumite Kyohan (p.24), but the author claims not to know its origins.