I ordered a 7" from the USA a few months ago, and after 5 weeks it hadn't arrived. I contacted the seller who swore blind that he'd posted it Airmail. The very next day it turned up absolutely soaking wet... and I mean ABSOLUTELY!! The record had been just slipped in bubblewrap in it's sleeve which had disintegrated due to the wet.... still played though Lordy knows what had happened to it on its journey!!
Apart from that I've never had stuff missing that's come to me, although I have had stuff go missing that I've sent out to people outside the UK. With this in mind I always now obtain proof of postage from the Post Office (you can download a form from the Royal Mail website). Of course, this doesn't make it any better for the buyer, but at least it proves you sent it when it comes down to a Paypal query or insurance refund.
Despite all the mentions of problems with Italy & France, I have never ever had an issue. Saying that though, an Italian friend of mine confirmed that the Italian postal service (especially in the Naples region) is absolutely rife with theft....