You have to talk like a man when dealing with these companies, and they'll do what you need. If order tracking shows "delivered" but the item is not on your doorstep, then Amazon will immediately reship your order while they track down the previous shipment, that's not your concern anymore. But you have to make them believe that is the only option you're willing to accept.
What will Fedex accomplish by sending someone else out tomorrow? He'll do the same thing you did and not locate the package. They were just dicking around with you, probably because you let them. Don't let them do that.