Quote:
was told they didn't have them, and haven't used them for a long time.
Unfortunately, that's a very common problem. Unlike commemorative and/or definitive stamps that are directly supplied to each post office on the date of issue, these high value stamps must be specifically ordered by the Postmaster in each location (presumably in sufficient quantity to meet local demand).
Those Postmasters who do not cater to a stamp collecting clientele are likely to forego ordering these stamps in the first place, as meters are easier for them to deal with, as they don't have to inventory a vast quantity of high value stamps that few people are likely to purchase on the retail level.
Local Postmasters often point to USA Philatelic as the means in which to acquire stamps the local post office doesn't carry.