I have no doubt that the buyer scammed you based on your story. However, you DID NOT protect yourself.
Misconception: Shipping Insurance is for the buyer's protection. WRONG!
Reality: Shipping Insurances protects the SELLER for lost shipments. It is the responsibility of the seller to deliver the item to the buyer. I learned this myself, just today as a matter of fact. This is an important lesson for new sellers, and I had never heard it before today.
I had a buyer who hadn't yet received his statues that I shipped out Jan. 10 (I know it hasn't been that long, but people on Ebay aren't the smartest). He didn't buy insurance, and I started checking around about whose responsibility it was. It was MY responsibility as a seller to get insurance if I wanted it. If the item got lost in the mail, then Paypal would see that it never got delivered. The buyer is protected through his/her Credit Card or Paypal, so shipping insurance for the buyer is not needed. Luckily, he e-mailed me today and told me that they arrived.
This doesn't relate to your post, but Always ship internationally with Global Express (EMS), UPS, FedEx, or DHL. I shudder to think of the expensive items I shipped internationally with Airmail Parcel Post before I really learned the ropes of being a seller. I wouldn't have been covered at all. I'll ONLY ship internationally with Global Express, for the reasons that JS and Gruson stated.
Jesse's advice is also good. NEVER leave money in your Paypal account. Always take it out immediately. There is no fee for an automatic transfer. Do it and do it often.
I've got 100% rating on Ebay as well, but I've had a few close calls. It can get scary, especially when dealing with REALLY expensive items. I had a problem with a $1,300 item I shipped to Spain once, which freaked me out.
DJ, if you had insured the item, then you could either get your money back that way or the Post Office could investigate and prove that it was delivered.
Also, always use signature confirmation on items that are $250 or over as required under the Seller Protection Policy.