All those problems existed in medieval Europe, including months-long delays or even years in case of war, and transactions nonetheless took place.
Essentially they worked by either
producing physical objects which act as the registry, either definitively, or until the transaction can be authoritatively recorded in a central registry
Making more people aware of the transaction, treating the general public or specific individuals as an ad-hoc registry
These were handled by letters of credit, akin to banker's drafts. In a nutshell, a bank in one location takes a deposit of gold or other valuables, and issues a letter which can be drawn on a bank in a distant location. For this to work the banks must have a stock of gold to draw against. For gold you can substitute uranium, plutonium or unobtainium. Letters of credit were easier to transport, conceal and protect from theft.
The primary responsibility for proving authenticity of such letters and detecting forgeries lay with the receiving bank, and many secret methods were used to verify them such as seals, embosses, secret marks, handwriting and so forth, just as today banknotes have anti-forgery holograms and watermarks.
Real estate transactions
To obtain good title to land, you would have possession of a bundle of documents (called "title deeds") proving a chain of title, from some original grant of title which is uncontested. Each document would be a deed setting out what title was transferred, any conditions attached (such as a duty to pay rent, a duty to pay towards maintenance of churches, limitations on permitted use and so forth).
To convey title (e.g. to sell the property) you would hand over the entire bundle, together with a new deed documenting the transfer. In this way the bundle grows with every transfer.
The advantages is that a central registry is not required, but this system can be combined with a system of registration, registering the title as it exists at certain points is a protection against loss of the documents or forgery.
Note that this is still commonplace in England even though England has now moved to a central registry system for recording title. For properties which haven't been transferred in the last few decades, the bundle is still definitive.
Witnesses, notarisation and publicity
Contracts and agreements are written in physical form which is difficult to alter, and witnessed by persons who give their name, and the location where they can be found. In case of dispute, these witnesses can testify that the contract is valid.
Notaries are a special case of witnesses. A trusted person can record a copy of the document (or just details of when the document was notarized, who signed etc), and keep it safe. In case of dispute, he can consult his records.
The general case of this is essentially "spreading it around". The agreement can be published in newspapers, posted in the town square, and so forth. As long as enough people know about the agreement, it becomes impractical to deny it.
So war agreements can be proved by announcing them widely:
posting in the public square,
broadcasting on radio and television,
Memorializing in stone tablets or monuments
having them cried about town by "town criers" (officials whose job it is to make public announcements):
"Hear ye, hear ye, hear ye! On Michaelmas his Majesty the King did treat with the King of France that ..."
having lavish ceremonies to celebrate the agreements with large public attendances attracted by free food, drink and entertainment.
The public ledger of crypto-currencies are a special case of this.
Two copies of the contract can be written side by side on a single piece of paper, and both signed and sealed by all parties. The document is then folded (indented, hence the name) and torn down the middle, so that each party has a copy. Proof that the two halves belong together is given by the shape of the tear, which is unique. Proof that the documents haven't been altered, is given by the difficulty of erasing the ink used. If words appear on one copy and not the other, then these must have been added later.
These were typically used for contracts for a number of years of personal service such as apprenticeships.
These were handled by "powers of attorney". (The word "attorney" means "appointed person").
You appoint a person in a distant location to exercise a limited power to undertake certain transactions on your behalf, and record the powers they have in a document using one of the above methods.
They then transmit to you what they have done in a similar method.
In this way you can enter into an agreement to buy a distant property (land in another country, or on another planet). An attorney in London will have instructions to sell the property. When you agree to buy, you get a physical document proving the agreement, which you take with you to your new residence in Northumbria. You present the letter to the attorney in the new location, who conveys title to you. This works because to take possession, you need to travel, and you take your proof of entitlement with you.
Sometimes ambassadors were given limited powers to enter into agreements on behalf of the sending country.