Are we talking an expensive item here?

I don't know how Ebay would 'rule' on this situation - you appear to have fulfilled your end of the bargain, and the only plausible explanation is theft from the mail (which is a rare event).

If it was not an expensive item, I would be tempted to hold my nose and make the customer happy, in order to preserve 100% positive feedback.

If a more expensive one, I would be more inclined to stand my ground. Its a subjective call, and it depends both on your read of the customer, as well as how important the $ is to you, and how much Ebaying you plan to do as a seller.

Hope this helps,

-Oke