I have no experience with caching food, so this may be of no use at all - or may be something you already considered.

How remote an area are you hiking? I'm wondering if you would be passing through, or near, a small town or village. Would there be a store or post office that would be willing to hold your cache for you? It might mean an extra mile or two of walking, but it would remove all doubt that it would be there. Of course, you'd need to time it to arrive when the facility was open. (And, if it's a store, it wouldn't hurt if you could buy something from them.)