Hi Dan, firstly I have to admit that I'm stunned at the lack of options available to you through the postal service there, quite bizarre.
I think what you will find is that PayPal will be looking for proof of postage more that actual tracking information, may be wrong, but that's my best guess. Now even though your postal service doesn't seem to provide basic tracking for registered items, they will have to provide you with a proof of postage receipt at the time of accepting the delivery for despatch.
First thing I would do is clarify the situation with PayPal, asking if a receipt for registered delivery will be acceptable as proof of postage for the, and that may well get you your cash back.
I would also be negotiating with the seller regarding the return of the item to them as it is not as it was listed. I would be making it quite clear to them that I would be showing my displeasure via their feedback should they not resolve this with a refund.
The only option you have open to you for filing a charge-back is paying via credit card. Then most cards will offer you a 3 month period to file, however I'm not sure you could file for a charge-back because the item was not as you thought. Once again, you would need to confirm, but my understanding is that a charge-back can only be filed in the event that you did not receive the item at all.
Hopefully some other may well have more information on that for you.
Of course filing a charge-back with PayPal is very straight forward if you don't actually receive the game, as then the onus is on the seller to provide proof of postage that the order was in fact sent, but that's not much help in this instance unfortunately.
Good luck with it.