There's the next sentence: "I saw Mr Brown ..... the building at two o'clock."
Which option would be the most appropriate to put in and why ? I really want to put in "was leaving", but there's no such option.
leave / to leave / having left
Leave is indeed the correct option. However, there is also some intuition behind this seemingly strange usage. Let's first clarify that was leaving is actually incorrect, so even if that option was given you still couldn't use it. To see this, we replace Mr.Brown by him. So we get I saw him.... Now we can see that the sentence that starts with him actually has no subject at all! So was is wrong since Mr.Brown isn't the subject anywhere at all!
However, we know that each sentence must have a subject. And yet, there is none here. In fact, this sentence is gramatically wrong since the modern English language doesn't allow for such constructions. The exact name of this construction of a sentence is Accusativus cum Infinitivo, and it is widely used in ancient languages such as Greek or Latin. What happens here is that the object (him) is taken to be the subject and the infinitive (leave) is taken to be the primal verb. So note that leave isn't a verb in the present tense but the full infinitive.
All in all, this is a rather antique construction that one can expect to find in ancient texts. So even though this usage might seem idiomatic, it was a common way of speaking a few thousand years ago.