Actually, I have had no problems with Amazon. First you have to realize that Amazon is an e-commerce front for:
1. Amazon itself.
2. Other vendors who let Amazon warehouse and ship their stuff.
3. Venders who just use Amazon to take the orders/payments.
The latter has the possibility for a decent amount of variability. But even with that everything I've ordered has beat or meets the 3 day "free" limits if it was listed in stock at the time of ordering.
AVS deals with billing addresses which is a mailing address and works fine with PO BOXES. I've had more problems with AMEX declining to accept things where the shipping address doesn't match the billing address or some other "known" address for me.
The PO box verifies just fine. The problem is that the USPS AVS system corrects the physical address (which technically is not a "street address," but rather a "911 address") to the PO Box, which makes sense for USPS because that's where the mail or parcel should go. It's also fine for credit card issuers and the like, who will accept a PO box if USPS says it's okay.
The problem arises when the shipper uses the USPS AVS system for packages being shipped via non-USPS carriers, which they're not supposed to do, but a lot of them do nonetheless. The physical address gets converted to the PO Box, and then when the UPS or FedEX system tries to print the shipping label, it pukes on the PO box.
Amazon gives you the option of overriding the result and just shipping to whatever address you specify, even if their system believes that its incorrect. Most other companies will do this with a phone call to customer service. A very few, such as NewEgg, can't (or won't) ever override it. As a result, I can't order anything from NewEgg. No big deal. MicroCenter is better, anyway -- and they'll ship to a tree house if you ask them to.
Just to complicate the issue a little bit more, even though no mail can be delivered to it, the physical address has its own ZIP suffix -- and it's different from the PO Box suffix (which is simply the PO box number preceded by a zero). This only rarely causes problems, and only with government agencies (like FAA) that require the physical address, even if the mail is going elsewhere.
What happens here, as best as I can understand, is that the ZIP suffix of a physical address can be used to pinpoint the location of a residence with great precision. But when the AVS conversion of the physical address happens, USPS correctly assigns the suffix as the PO box preceded by a zero. That's what it should be for mailing purposes, but systems that want the physical address for security reasons barf on it.
It took me several days and five hours of phone calls to change the address on my driver's license -- and they still got it wrong. I finally gave up and visited the county clerk (who also does the DMV stuff), who was able to override it in seconds. The FAA system also puked when I tried to change my address online. I forget how I got it fixed. I think I had to mail it in with a check and a letter from the postmaster.
All this PO box stuff really annoyed me at first because I'd say that one-half to three-quarters of the online shopping I did required a phone call to customer service to override the AVS system. Correcting the address to the PO box solves the problem with banks and such wanting a physical address, but it created new ones for non-USPS shipments.
Since then, however, it seems that more companies are allowing the customers to override the AVS results themselves. The tire company I ordered from yesterday initially barfed on the address, but did let me override it. I suppose shippers got a lot of complaints from annoyed customers and got tired of wasting their CSRs' time doing manual overrides. Most people do know their own addresses, after all.
-Rich