I have seen this and it is normal, well usually. The part of information that is missing here is understanding the route that the agent takes to talk to the BES server. If there are multiple relays between that client and the BES server, then the content has to be deployed to all the relays in the chain.
You mention that you used the “File Pre-cache Wizard”, but did you pre-cache it to all the relays in the chain?
Is it possible that the target client moved to a different relay?
Martin