Unless you strike it lucky and are buying a one-owner bike from a well-organised individual it's totally unrealistic to start expecting bits of paper proving the seller actually owns the bike or a receipt to show when they bought it brand new. I have only bought one secondhand bike like that, but such transactions are the exception not the norm. If you are buying older steel bikes in particular, most will have had several owners by now, and as things get older and less valuable, buyers and sellers become less interested in maintaining paper audit trails. They just want a functional bike. I've even bought cars without logbooks before now, you just have to make a judgement on the vendor and factor in whether the price is a good bargain.
The reality is most people with multiple bikes, have a good chance of having a stolen one amongst them, even if the seller they bought from was honest. Bikes are at their most valuable and attractive to thieves, when they are still fairly new. You might buy a 25 year old bike that was stolen when only one or two years old, then bought by an innocent owner from the thief, and subsequently bought and sold several times since, always in good faith. Only the thief would know the truth, and all the subsequent owners would believe the bike was kosher, because they had always done straight deals. Most owners don't record frame numbers, and they are not centrally registered unlike cars, so most stolen bikes cannot ever be positively identified as such. I would not knowingly buy a stolen bike, but at the same time I don't stress about the possibility that one of mine could have been nicked at one stage in it's life, even if a couple of owners ago. It's like worrying that the banknote you were handed as change in a shop might have previously been taken in a robbery.
