I have never heard of anyone letting military people OCONUS (from the US) without leave. With the ATFP briefings required, reporting contact with foreigners as well as tracking US military personnel in foreign countires (yes, they do that to a degree), it would probably be against at least one DoD reg and just plain stupid to do otherwise.
Now that I think more about it, as a former AT officer I am pretty sure that everyone going to a foreign country needed prior approval before going. I think it required NCIS notification of some kind and SSO approval if you had a TS SCI. Just so you know, unreported travel is a giant red flag for background investigations and security clearances, even to relatively 'benign' countries like Singapore and Japan.