The problem is that it isn't cost-effective for large national players to fight for this business, and small players face powerful barriers to entry.

One potentially viable solution to addressing this problem might be an adaptation of the "Shipping Consolidator" business model (http://en.wikipedia.org/wiki/Package_delivery#Role_of_parcel...).

Shipping consolidators pick up a shipper's parcels, sort and route them, then enter them into the Postal system for final delivery.

A shipping consolidator startup would be able to offer many of the value-added services on your wishlist without facing the barriers of starting a stand-alone national carrier or the limitations associated with local/regional carriers.

Of course, you lose control of the actual handling of the package after turning it over to a 3rd party carrier. Still, I'd imagine that a shipping consolidator using RFID data could develop a sufficiently sophisticated predictive model capable of providing much more accurate delivery estimates than those provided by the UPS, FedEX, et al.