Given the number of people on Earth and the countless decisions and actions they take in each moment, it's statistically impossible for extraordinary coincidences to NOT happen. But it's still kinda mind-blowing, isn't it?

It doesn't seem like that unusual to me. You said you had a lot in common. That means you shared many of the same experiences. Apparently including sometimes travelling to Brisbane.

We tend to single out coincidences because they surprise us but think of all of the people you meet. And then realize that such an actuality could manifest with any of them.

This is similar to the surprising chance that in a small group of people at least two will share the same birthday.

The key word in your story is "recognized". Because you didn't know each other you may have passed each other many times without noticing but once you had met then recognition captures your attention.

Here is a site that helps with your question... [quora.com]

Probability law...

By it's definition, no. You run into thousands of people from all walks of like all the time and never think twice about it, but wow, what a coincidence to run into someone you do know! My ex would tell me about looking at the odometer and seeing a number like 777777 or 234567 and think that it's a cosmic message being sent to her; I tell her that she probably unconsciously looks at the odometer all the time with nary a thought about it, except for the occasion that the numbers happen to line up in some memorable way that appears beyond coincidental, But that's all it is... a coincidence.

Maybe your local travel agent sells the same itinerary to a lot of people.

While living in British Columbia before we met, my wife received a phone call from a long distance company to sell her their product. After some conversation, it turned out his aunt lived next door to my wife when she lived in a little shire in northern Scotland, an hour outside Inverness.

It happens.

I can't help myself...
Karma is simply a pre Einstein explanation of cause and effect.
Anyhow coincidence is just probability with variables we don't know about or too numerous to work out. Its tempting to believe its 'fate' saves trying to work it all out and gives it a 'specialness'

That is simple enough. Things happen all the time, day in and day out. Enough happenings all at once mean coincidences, even extraordinary ones are bound to occur and they seem significant to us because humans are especially good at seeing patterns.

What would make it surprising is if someone predicted when this would happen, ahead of the event. Think like how lottery numbers of "1,2,3,4,5,6" are just as likely as any other group of 6 numbers (assuming a fair lottery choosing six numbers, no repeats) but looks more surprising than the other groupings that don't look patterned to us.

Cairns reminds me of fruit bats

It is probability. Think of it in terms of statistics: averages are made up of extremes. In other words, if you wanted to find the average household income in an area, and let's say it's $50,000, that's going to include the households scraping by on $15,000 as well as those making over $100,000. It would be awfully strange, in fact, if everyone actually made the average. Well, probabilities are similar. If coincidences never happened, it would be awfully strange — but from a subjective perspective, the clustered events we encounter seem strange to us. In reality, if we could take all events as a snapshot, we'd see an even distribution of things that never intersect and less frequently some mild coincidences, and very rarely some extraordinary coincidences. (And on the other side you'd see a lack of intersection where you'd expect to see some, but we rarely take notice of things that don't happen.) Another example: The odds of you winning the lottery are slim. The odds of someone winning the lottery are high. From your perspective, it's seems so strange that you won, but someone was going to win, and it would seem highly improbable from anyone's perspective. If you won a second time, a couple of years later, that seems incredible. But, again, from a non-subjective perspective, it's very likely that such things happen occasionally, but it's from the subjective view that it seems so unlikely.

I got nothin'. Sometimes shit just happens.

What are the odds? The lottery here in the UK runs at odds of 1 in 14 million of hitting the jackpot, yet it still happens. If enough people play the game, then some will win. And everyone's playing some flavour of the "randomly meeting someone you know" game every day.

You'd be telling much the same story if you'd bumped into anyone you knew from the UK in Brisbane, so also factor in the number of people you know in the UK. The odds come down considerably. So what are the odds of this happening to someone? (Not necessarily you.) And what are the odds of them telling that story? I'm betting it happens more often than you'd imagine.

You are probably one of a very small number of people who've had this happen so remotely. Chances are, it'll never happen to you again. I've had similar happen once but more locally: I was driving along the motorway and spotted a colleague going to a completely different destination in the car next to me, over 100 miles from the office. I too thought "What are the odds?" I'm not sure what they are, but it's happened only once in nearly 30 years of working for the same company.

Well, if you wanted to go about scientifically, she and you could sit down and draw up the plans that show what both of you were doing since you left England. There are probably many points where your routes could have intersected ( well, one of them did) There is nothing supernatural going on. There are now so many people in this world, it is a wonder not everybody runs into somebody they knew when... What a great experience!

Coincidence is just that ...a coincidence...things happen, some are totally unexpected others could be predictable. I have had similar experiences of running into my neighbour halfway around the globe at a really obscure destination. We went for a beer and had a good laugh!

I believe in Einstein. He said that all matter is really energy. Thus since energy can't be destroyed or created, we have always existed and will always exist in energy form.

We contribute to creating our own reality:

"For us believing physicists, the distinction between past, present and future is only a stubbornly persistent illusion." -Einstein

“I regard consciousness as fundamental, and matter as derivative from consciousness." – Max Planck, theoretical physicist who originated quantum theory, 1918 Nobel Prize in Physics

Yes it can, we call it maths.
I love coincidences. A few years back I was camping in this forest, next morning a golden lab came for a chat. He seemed familiar. Owner came to get him. We had a chat, I had just come back from houseboating up the Nambucca River, he and his dog were staying where we disembarked and I had been playing with the dog. That may be strange enough, except, we stopped in at home for 2 days on the way back, the guy and his dog continued their travels, and he stayed with his sister, who just happened to live across the road from us.
So, we ran into this dog 3 times in a week, 3 different places across 2 states.

If someone to dealt out a pack of cards between 4 people and each person got dealt an entire suit. You probably think that someone was cheating and you would probably be correct. However given the number of bridge hands dealt in the course of a year. Probability suggests that it has happened 5 times since the games inception. How many places have you been? How many places have others been? You think about an old friend that you havent spoken to for ages. The phone rings and its them. How many times did you think about them and it didn`t? How many other people have you thought about? We had a poker night once that produced 3 royal flushes!
[archive.spectator.co.uk]

There is no reason to believe either fate or coincidence exist. Both imply there is some meaning to apply to events that occur, but no such meaning is evident or necessary for the event to occur.

I experience synchronicity all the time, the weird kind that Carl Jung describes. I try not to think about it too hard, and dismiss it as attribution bias or delusions of reference.

There was a glitch in the matrix and it had to reset. In reality it's incredible how we can be caught up in our own lives and social circles that we may never notice the people we pass by on the street. I have a friend that I met at a political organizing group and it turned out he only lives six houses down from me. So your not alone it's just something that happens from time to time.

We as a species seem to have a tendency to think coincidences are a lot more remarkable than they actually. are. The most commonly given example to demonstrate this is the so-called Birthday Problem: how many people need to gather together for it to become more likely than not that two of them will share the same birthday?

Many people immediately answer 366 as there are a maximum of 366 possible birthdays in a year, whereas others halve that number. In fact, probability shows us that the likelihood exceeds 50% in a group of just 23 people (if you like maths, it's explained on this Wikipedia page: [en.wikipedia.org]

There are a huge but finite number of humans alive, and a huge but finite number of places they can be. This coincidence is a statistically inevitability; it had to happen to somebody and that somebody was you, and possibly many other people all over the world at almost exactly the same time. Meanwhile a star somewhere in the universe shone it's last light, and began to collapse into itself.

The mystery of massive numbers isn't that they allow for incredible things to become be commonplace, it's that we think those things are incredible in the first place.

My oldest became friends with a boy in his school when we lived in Huntsville, Tx. We then moved to Colorado Springs, CO and lo and behold the boy was at his school. A couple of years later we moved to New Caney, Tx and guess what? Yep, the boy had moved there.

My youngest son would come to me all the time and tell me that his father was coming over. Always, within 24hrs he would make an appearance. One time he lived 900 miles away when my son told me and neither one of us knew he was coming over. Still haven't figured that one out.