An observation: We have mailed various things to China. Anything more than an ordinary letter that didn't require a signature never got there. This includes things like cards.
Since it was only a delivery signature that mattered we figured it was the local delivery guy that was the problem.