The mean post office lady was wrong. If you're living in a country with a large US Embassy, chances are that there will be an APO inside the chancery. Although technically, they're not supposed to purchase postage on your behalf, one of the consular officers may be extremely sympathetic, or could at least tell you where you could get some postage. If you tell me which embassy, I could probably tell you what your chances are.