I ordered a tablet from gearbest on 29 June. On 30 June they sent me an email claiming it had been shipped and that I can "check the shipping progress and location of the package on Australia post Registered". The link just goes to their website and the number is not a valid Australia Post tracking number. Invalid tracking is a strong fraud indicator in my experience.
How long should I wait before contacting Paypal?
allow 2-3 weeks for delivery. it is normal (at least in my last purchase) for their tracking not to work, so don't stress.
What does the tracking number start with?
If it's "RP", try SingPost's tracking: http://www.singpost.com/
Would Australia Post return a valid record if the article did not originate from an Australia Post outlet?
Put the tracking number in this site and it will find the correct courier, most likely it will be SingPost.
They won't work here until the package hits Australia
this site usually works for my Gearbest orders.
http://www.trackingex.com/china-post-tracking/?utm_source=go…
The goods arrived the next day. Meanwhile I logged a support ticket with Gearbest. They sent back an email with an invalid link for me to track its progress.
I've ordered 3 things from gearbest. A torch and two xiaomi mibands. I've never gotten the tracking to work and they've all arrived OK. Took an age though.