[dedward]

While this is all true - stolen passports are a very real problem, and when I had mine stolen, and got a replacement, it clearly said on one of the first pages "This passport replaces passport #XXXXXXX reported stolen on DATE".

Yes, I lost all my visa/entry stamps.... and yes, that can be a problem - but the fact is, a nation is unlikely to hold you hostage and create a diplomatic incident because your passport has been stolen.