It is funny that you should bring this up, because I was very tempted to start a thread on this very topic about a week ago. I have been having the same problem. I went to one post office here on campus and they told me that they had nothing. I went to a second post office downtown and was told that yes, they had a few, but that they were for customers only (what the fuck am I then?). I went to a third contract post office that no one goes to (very bad post office) and they had a few for me, and then I went to the main branch downtown and got a few more. In the meantime, I went ahead and ordered some online. I know what boxes you are talking about, and they are quite handy.
It definitely seems to me that they are phasing out carrying these in the offices and making people order them online. I am not sure why though, since they pay for the shipping to send them to you. I would think that they would want to make it as easy as possible to get PM boxes so that you don't go to FedEx or UPS.
Chris