I lost both of my original logbooks in my home when in washed away due to a hurricane. I was military trained.... and yes... lost my military flight records as well. That said.... I do have proof of my UPT training and follow on training in the military. I called my FSDO and spoke with one of the inspectors. Their advice was to create another logbook and single line entry each aircraft to the best of my knowledge ( I took 10% off the hours I knew I had logged ). I then placed a notarized statement in the front of the logbook ( their idea ) stating how the logs were lost and how I derived the hours I had entered above. I went to my 121 interview and was hired befor I got to the airport for the flight home. The CP who reviewed my records asked a few questions but did not seem alarmed in the least. I now work for a 91/135 outfit and also had no problems. In my case it hasnt been a problem...yet. FWIW, I also now use an electronic log.